#include <bits/stdc++.h>
namespace tools {
template <typename T>
constexpr T quo(const T& lhs, const T& rhs) {
  return lhs > static_cast<T>(0)   ? lhs / rhs
         : rhs > static_cast<T>(0) ? -((-lhs - 1 + rhs) / rhs)
                                   : (-lhs - 1 + -rhs) / -rhs;
}
}  // namespace tools
namespace tools {
namespace detail {
namespace is_prime {
constexpr std::uint_fast32_t mid(const std::uint_fast32_t low,
                                 const std::uint_fast32_t high) {
  return (low + high) / 2;
}
constexpr std::uint_fast32_t ceilsqrt(const std::uint_fast32_t n,
                                      const std::uint_fast32_t low,
                                      const std::uint_fast32_t high) {
  return low + 1 >= high                          ? high
         : (mid(low, high) * mid(low, high) == n) ? mid(low, high)
         : (mid(low, high) * mid(low, high) < n)
             ? ceilsqrt(n, mid(low, high), high)
             : ceilsqrt(n, low, mid(low, high));
}
constexpr std::uint_fast32_t ceilsqrt(const std::uint_fast32_t n) {
  return n < 3 ? n
               : ceilsqrt(
                     n, 1,
                     std::uint_fast32_t(1)
                         << (std::numeric_limits<std::uint_fast32_t>::digits /
                             2));
}
constexpr bool find_factor(const std::uint_fast32_t n,
                           const std::uint_fast32_t low,
                           const std::uint_fast32_t high) {
  return low + 1 >= high ? (n % (2 * low + 1)) == 0
                         : (find_factor(n, low, mid(low, high)) ||
                            find_factor(n, mid(low, high), high));
}
}  // namespace is_prime
}  // namespace detail
constexpr bool is_prime(const std::uint_fast32_t n) {
  return n > 1 &&
         (n == 2 ||
          (n % 2 == 1 &&
           (n == 3 || !detail::is_prime::find_factor(
                          n, 1, (detail::is_prime::ceilsqrt(n) + 1) / 2))));
}
}  // namespace tools
namespace tools {
template <typename T,
          typename ::std::enable_if<::std::is_unsigned<T>::value,
                                    ::std::nullptr_t>::type = nullptr>
constexpr T rotate_left(const T& value, const ::std::size_t& count) noexcept {
  return (value << (count & ::std::numeric_limits<T>::max())) |
         (value >> (-(count & ::std::numeric_limits<T>::max()) &
                    ::std::numeric_limits<T>::max()));
}
template <typename T,
          typename ::std::enable_if<::std::is_signed<T>::value,
                                    ::std::nullptr_t>::type = nullptr>
T rotate_left(const T& value, const ::std::size_t& count) {
  return value >= static_cast<T>(0)
             ? static_cast<T>(::tools::rotate_left(
                   static_cast<typename ::std::make_unsigned<T>::type>(value),
                   count))
             : (throw ::std::invalid_argument("value of ::tools::rotate_left "
                                              "must be non-negative, but was " +
                                              ::std::to_string(value) + "."));
}
}  // namespace tools
namespace tools {
template <typename T>
class monoid {
 private:
  ::std::function<T(T, T)> m_operation;
  T m_identity;

 public:
  monoid(const ::std::function<T(T, T)>& operation, const T& identity)
      : m_operation(operation), m_identity(identity) {}
  monoid(const ::tools::monoid<T>&) = default;
  monoid(::tools::monoid<T>&&) = default;
  ::tools::monoid<T>& operator=(const ::tools::monoid<T>&) = default;
  ::tools::monoid<T>& operator=(::tools::monoid<T>&&) = default;
  virtual ~monoid() = default;
  T operation(const T& x, const T& y) const { return this->m_operation(x, y); }
  const T& identity() const { return this->m_identity; }
  template <typename U = T,
            typename ::std::enable_if<::std::is_integral<U>::value,
                                      ::std::nullptr_t>::type = nullptr>
  static ::tools::monoid<U> multiplies() {
    return ::tools::monoid<U>(::std::multiplies<U>(), 1);
  }
};
}  // namespace tools
namespace tools {
template <typename T>
void read(::std::istream& is, ::std::vector<T>& vector,
          const typename ::std::vector<T>::size_type size) {
  vector.reserve(size);
  ::std::copy_n(::std::istream_iterator<T>(is), size,
                ::std::back_inserter(vector));
}
template <typename T>
void read(::std::vector<T>& vector,
          const typename ::std::vector<T>::size_type size) {
  ::tools::read(::std::cin, vector, size);
}
template <typename T, ::std::size_t N>
void read(::std::istream& is, ::std::array<T, N>& array) {
  ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
}
template <typename T, ::std::size_t N>
void read(::std::array<T, N>& array) {
  ::tools::read(::std::cin, array);
}
}  // namespace tools
namespace tools {
template <typename T>
constexpr T mod(const T& lhs, const T& rhs) {
  return lhs - ::tools::quo(lhs, rhs) * rhs;
}
}  // namespace tools
namespace tools {
namespace detail {
namespace extgcd {
template <typename T>
class result {
 public:
  T gcd;
  T x0;
  T y0;
  result() = default;
  result(const T& gcd, const T& x0, const T& y0) : gcd(gcd), x0(x0), y0(y0) {}
};
}  // namespace extgcd
}  // namespace detail
template <typename T>
::tools::detail::extgcd::result<T> extgcd(T prev_r, T r) {
  T prev_s = 1;
  T prev_t = 0;
  T s = 0;
  T t = 1;
  while (r != 0) {
    const T q = ::tools::quo(prev_r, r);
    const T next_r = prev_r - q * r;
    prev_r = r;
    r = next_r;
    const T next_s = prev_s - q * s;
    prev_s = s;
    s = next_s;
    const T next_t = prev_t - q * t;
    prev_t = t;
    t = next_t;
  }
  return ::tools::detail::extgcd::result<T>(std::abs(prev_r), prev_s, prev_t);
}
}  // namespace tools
namespace tools {
template <typename T>
class vector2 {
 public:
  T x;
  T y;
  vector2() : vector2(T(), T()) {}
  vector2(const T& x, const T& y) : x(x), y(y) {}
  double norm() const { return ::std::sqrt(this->squaredNorm()); }
  T squaredNorm() const { return this->inner_product(*this); }
  template <typename SFINAE_T = T,
            typename ::std::enable_if<::std::is_same<SFINAE_T, double>::value,
                                      ::std::nullptr_t>::type = nullptr>
  double normalize() const {
    return *this / this->norm();
  }
  ::tools::vector2<T> operator+() const { return *this; }
  ::tools::vector2<T> operator-() const {
    return ::tools::vector2<T>(-this->x, -this->y);
  }
  friend ::tools::vector2<T> operator+(const ::tools::vector2<T>& lhs,
                                       const ::tools::vector2<T>& rhs) {
    return ::tools::vector2<T>(lhs.x + rhs.x, lhs.y + rhs.y);
  }
  friend ::tools::vector2<T> operator-(const ::tools::vector2<T>& lhs,
                                       const ::tools::vector2<T>& rhs) {
    return ::tools::vector2<T>(lhs.x - rhs.x, lhs.y - rhs.y);
  }
  template <typename OTHER,
            typename ::std::enable_if<
                !::std::is_same<OTHER, ::tools::vector2<T>>::value,
                ::std::nullptr_t>::type = nullptr>
  friend ::tools::vector2<T> operator*(const ::tools::vector2<T>& lhs,
                                       const OTHER& rhs) {
    return ::tools::vector2<T>(lhs.x * rhs, lhs.y * rhs);
  }
  template <typename OTHER,
            typename ::std::enable_if<
                !::std::is_same<OTHER, ::tools::vector2<T>>::value,
                ::std::nullptr_t>::type = nullptr>
  friend ::tools::vector2<T> operator*(const OTHER& lhs,
                                       const ::tools::vector2<T>& rhs) {
    return ::tools::vector2<T>(lhs * rhs.x, lhs * rhs.y);
  }
  template <typename OTHER,
            typename ::std::enable_if<
                !::std::is_same<OTHER, ::tools::vector2<T>>::value,
                ::std::nullptr_t>::type = nullptr>
  friend ::tools::vector2<T> operator/(const ::tools::vector2<T>& lhs,
                                       const OTHER& rhs) {
    return ::tools::vector2<T>(lhs.x / rhs, lhs.y / rhs);
  }
  T inner_product(const ::tools::vector2<T>& other) const {
    return this->x * other.x + this->y * other.y;
  }
  ::tools::vector2<T>& operator+=(const ::tools::vector2<T>& other) {
    return *this = *this + other;
  }
  ::tools::vector2<T>& operator-=(const ::tools::vector2<T>& other) {
    return *this = *this - other;
  }
  template <typename OTHER,
            typename ::std::enable_if<
                !::std::is_same<OTHER, ::tools::vector2<T>>::value,
                ::std::nullptr_t>::type = nullptr>
  ::tools::vector2<T>& operator*=(const OTHER& other) {
    return *this = *this * other;
  }
  template <typename OTHER,
            typename ::std::enable_if<
                !::std::is_same<OTHER, ::tools::vector2<T>>::value,
                ::std::nullptr_t>::type = nullptr>
  ::tools::vector2<T>& operator/=(const OTHER& other) {
    return *this = *this / other;
  }
  friend bool operator==(const ::tools::vector2<T>& lhs,
                         const ::tools::vector2<T>& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y;
  }
  friend bool operator!=(const ::tools::vector2<T>& lhs,
                         const ::tools::vector2<T>& rhs) {
    return lhs.x != rhs.x || lhs.y != rhs.y;
  }
  static ::std::array<::tools::vector2<T>, 4> four_directions() {
    return ::std::array<::tools::vector2<T>, 4>(
        {::tools::vector2<T>(static_cast<T>(-1), static_cast<T>(0)),
         ::tools::vector2<T>(static_cast<T>(1), static_cast<T>(0)),
         ::tools::vector2<T>(static_cast<T>(0), static_cast<T>(-1)),
         ::tools::vector2<T>(static_cast<T>(0), static_cast<T>(1))});
  }
  static ::std::array<::tools::vector2<T>, 8> eight_directions() {
    return ::std::array<::tools::vector2<T>, 8>(
        {::tools::vector2<T>(static_cast<T>(-1), static_cast<T>(-1)),
         ::tools::vector2<T>(static_cast<T>(-1), static_cast<T>(0)),
         ::tools::vector2<T>(static_cast<T>(-1), static_cast<T>(1)),
         ::tools::vector2<T>(static_cast<T>(0), static_cast<T>(-1)),
         ::tools::vector2<T>(static_cast<T>(0), static_cast<T>(1)),
         ::tools::vector2<T>(static_cast<T>(0), static_cast<T>(-1)),
         ::tools::vector2<T>(static_cast<T>(1), static_cast<T>(-1)),
         ::tools::vector2<T>(static_cast<T>(1), static_cast<T>(0)),
         ::tools::vector2<T>(static_cast<T>(1), static_cast<T>(1))});
  }
};
}  // namespace tools
namespace std {
template <typename T>
::std::string to_string(const ::tools::vector2<T>& f) {
  return '(' + ::std::to_string(f.x) + ", " + ::std::to_string(f.y) + ')';
}
template <typename T>
struct hash<::tools::vector2<T>> {
  using result_type = ::std::size_t;
  using argument_type = ::tools::vector2<T>;
  ::std::size_t operator()(const ::tools::vector2<T>& key) const {
    static const ::std::hash<T> hash;
    static const ::std::size_t shift =
        ::std::numeric_limits<::std::size_t>::digits / 2;
    const ::std::size_t hash_x = hash(key.x);
    const ::std::size_t hash_y = hash(key.y);
    return hash_x ^ ::tools::rotate_left(hash_y, shift);
  }
};
template <typename T>
::std::ostream& operator<<(::std::ostream& os,
                           const ::tools::vector2<T>& self) {
  return os << ::std::to_string(self);
}
template <typename T>
::std::istream& operator>>(::std::istream& is, ::tools::vector2<T>& self) {
  return is >> self.x >> self.y;
}
}  // namespace std
namespace tools {
template <typename T>
T square(const ::tools::monoid<T>& monoid, const T& x) {
  return monoid.operation(x, x);
}
template <typename T>
T square(const T& x) {
  return ::tools::square(::tools::monoid<T>::multiplies(), x);
}
}  // namespace tools
namespace tools {
template <typename T>
class group : public ::tools::monoid<T> {
 private:
  ::std::function<T(T)> m_inverse;

 public:
  group(const ::std::function<T(T, T)>& operation, const T& identity,
        const ::std::function<T(T)>& inverse)
      : ::tools::monoid<T>(operation, identity), m_inverse(inverse) {}
  group(const ::tools::group<T>&) = default;
  group(::tools::group<T>&&) = default;
  ::tools::group<T>& operator=(const ::tools::group<T>&) = default;
  ::tools::group<T>& operator=(::tools::group<T>&&) = default;
  virtual ~group() = default;
  T inverse(const T& x) const { return this->m_inverse(x); }
  template <typename U = T,
            typename ::std::enable_if<::std::is_integral<U>::value,
                                      ::std::nullptr_t>::type = nullptr>
  static ::tools::group<U> plus() {
    return ::tools::group<U>(::std::plus<U>(), 0, ::std::negate<U>());
  }
};
}  // namespace tools
namespace tools {
template <typename T>
T gcd(const T& a, const T& b) {
  return ::tools::extgcd(a, b).gcd;
}
}  // namespace tools
namespace tools {
template <typename T>
T pow(const ::tools::monoid<T>& monoid, const T& base,
      const std::size_t exponent) {
  return exponent == 0 ? monoid.identity()
         : exponent % 2 == 0
             ? ::tools::square(monoid, ::tools::pow(monoid, base, exponent / 2))
             : monoid.operation(::tools::pow(monoid, base, exponent - 1), base);
}
template <typename T>
T pow(const T& base, const std::size_t exponent) {
  return ::tools::pow(::tools::monoid<T>::multiplies(), base, exponent);
}
}  // namespace tools
namespace tools {
namespace detail {
namespace cumsum {
template <typename Iterator>
class monoid1d {
 private:
  using T = typename ::std::iterator_traits<Iterator>::value_type;
  ::tools::monoid<T> monoid;
  ::std::vector<T> from_left;
  ::std::vector<T> from_right;

 public:
  monoid1d(const ::tools::monoid<T>& monoid, const Iterator& begin,
           const Iterator& end)
      : monoid(monoid),
        from_left({monoid.identity()}),
        from_right({monoid.identity()}) {
    ::std::vector<T> source;
    ::std::copy(begin, end, ::std::back_inserter(source));
    this->from_left.reserve(source.size() + 1);
    for (const T& source_i : source) {
      this->from_left.push_back(
          monoid.operation(this->from_left.back(), source_i));
    }
    ::std::reverse(source.begin(), source.end());
    this->from_right.reserve(source.size() + 1);
    for (const T& source_i : source) {
      this->from_right.push_back(
          monoid.operation(this->from_right.back(), source_i));
    }
    ::std::reverse(this->from_right.begin(), this->from_right.end());
  }
  T operator()(const ::std::size_t l, const ::std::size_t r) const {
    if (l == 0) {
      return this->from_left[r];
    } else if (r + 1 == this->from_right.size()) {
      return this->from_right[l];
    } else {
      throw ::std::runtime_error("Unsupported operation.");
    }
  }
};
template <typename Iterator>
class group1d {
 private:
  using T = typename ::std::iterator_traits<Iterator>::value_type;
  ::tools::group<T> group;
  ::std::vector<T> preprocessed;

 public:
  group1d(const ::tools::group<T>& group, const Iterator& begin,
          const Iterator& end)
      : group(group), preprocessed({group.identity()}) {
    for (Iterator it = begin; it != end; ++it) {
      this->preprocessed.push_back(
          group.operation(this->preprocessed.back(), *it));
    }
  }
  T operator()(const ::std::size_t l, const ::std::size_t r) const {
    return this->group.operation(this->preprocessed[r],
                                 this->group.inverse(this->preprocessed[l]));
  }
};
template <typename Iterator>
class group2d {
 private:
  using OuterT = typename ::std::iterator_traits<Iterator>::value_type;
  using T =
      typename ::std::iterator_traits<typename OuterT::iterator>::value_type;
  ::tools::group<T> group;
  ::std::vector<::std::vector<T>> preprocessed;

 public:
  group2d(const ::tools::group<T>& group, const Iterator& begin,
          const Iterator& end)
      : group(group),
        preprocessed(::std::distance(begin, end) + 1,
                     ::std::vector<T>(
                         (begin == end ? 0
                                       : ::std::distance(::std::begin(*begin),
                                                         ::std::end(*begin))) +
                             1,
                         group.identity())) {
    const ::std::size_t height = ::std::distance(begin, end);
    const ::std::size_t width =
        begin == end
            ? 0
            : ::std::distance(::std::begin(*begin), ::std::end(*begin));
    {
      Iterator it1 = begin;
      for (::std::size_t y = 0; y < height; ++y, ++it1) {
        auto it2 = ::std::begin(*it1);
        for (::std::size_t x = 0; x < width; ++x, ++it2) {
          this->preprocessed[y + 1][x + 1] =
              group.operation(this->preprocessed[y + 1][x], *it2);
        }
      }
    }
    for (::std::size_t x = 0; x < width; ++x) {
      for (::std::size_t y = 0; y < height; ++y) {
        this->preprocessed[y + 1][x + 1] = group.operation(
            this->preprocessed[y][x + 1], this->preprocessed[y + 1][x + 1]);
      }
    }
  }
  T operator()(const ::std::size_t x1, const ::std::size_t y1,
               const ::std::size_t x2, const ::std::size_t y2) const {
    T tmp =
        this->group.operation(this->preprocessed[y2][x2],
                              this->group.inverse(this->preprocessed[y2][x1]));
    tmp = this->group.operation(
        tmp, this->group.inverse(this->preprocessed[y1][x2]));
    return this->group.operation(tmp, this->preprocessed[y1][x1]);
  }
};
}  // namespace cumsum
}  // namespace detail
template <typename Iterator>
::std::function<typename ::std::iterator_traits<Iterator>::value_type(
    ::std::size_t, ::std::size_t)>
cumsum1d(const ::tools::monoid<
             typename ::std::iterator_traits<Iterator>::value_type>& monoid,
         const Iterator& begin, const Iterator& end) {
  return ::tools::detail::cumsum::monoid1d<Iterator>(monoid, begin, end);
}
template <typename Iterator>
::std::function<typename ::std::iterator_traits<Iterator>::value_type(
    ::std::size_t, ::std::size_t)>
cumsum1d(const ::tools::group<
             typename ::std::iterator_traits<Iterator>::value_type>& group,
         const Iterator& begin, const Iterator& end) {
  return ::tools::detail::cumsum::group1d<Iterator>(group, begin, end);
}
template <typename Iterator>
::std::function<typename ::std::iterator_traits<typename ::std::iterator_traits<
    Iterator>::value_type::iterator>::value_type(::std::size_t, ::std::size_t,
                                                 ::std::size_t, ::std::size_t)>
cumsum2d(const ::tools::group<
             typename ::std::iterator_traits<typename ::std::iterator_traits<
                 Iterator>::value_type::iterator>::value_type>& group,
         const Iterator& begin, const Iterator& end) {
  return ::tools::detail::cumsum::group2d<Iterator>(group, begin, end);
}
}  // namespace tools
namespace tools {
template <::std::uint_fast32_t P>
class int_mod {
 private:
  ::std::uint_fast32_t m_value;
  constexpr static ::std::uint_fast32_t add_impl(
      const ::std::uint_fast32_t lhs, const ::std::uint_fast32_t rhs) {
    return lhs + rhs - (lhs + rhs >= P ? P : 0u);
  }
  constexpr static ::std::uint_fast32_t sub_impl(
      const ::std::uint_fast32_t lhs, const ::std::uint_fast32_t rhs) {
    return lhs - rhs + (lhs < rhs ? P : 0u);
  }
  constexpr static ::std::uint_fast32_t mul_impl(
      const ::std::uint_fast32_t lhs, const ::std::uint_fast32_t rhs) {
    return static_cast<::std::uint_fast32_t>(
        static_cast<::std::uint_fast64_t>(lhs) *
        static_cast<::std::uint_fast64_t>(rhs) %
        static_cast<::std::uint_fast64_t>(P));
  }
  constexpr ::tools::int_mod<P> pow_impl(
      const ::std::uint_fast32_t exponent) const {
    return ::tools::pow(
        ::tools::monoid<::tools::int_mod<P>>(
            ::std::multiplies<::tools::int_mod<P>>(), ::tools::int_mod<P>(1)),
        *this, exponent);
  }

 public:
  int_mod() : m_value(0) {}
  explicit int_mod(const ::std::int_fast64_t& value)
      : m_value(static_cast<::std::uint_fast32_t>(
            ::tools::mod<std::int_fast64_t>(value, P))) {}
  int_mod(const ::tools::int_mod<P>& other) : int_mod(other.m_value) {}
  constexpr explicit operator ::std::uint_fast32_t() const {
    return this->m_value;
  }
  ::tools::int_mod<P>& operator=(const ::tools::int_mod<P>& other) {
    this->m_value = other.m_value;
    return *this;
  }
  constexpr friend bool operator==(const ::tools::int_mod<P>& lhs,
                                   const ::tools::int_mod<P>& rhs) {
    return lhs.m_value == rhs.m_value;
  }
  constexpr friend bool operator!=(const ::tools::int_mod<P>& lhs,
                                   const ::tools::int_mod<P>& rhs) {
    return lhs.m_value != rhs.m_value;
  }
  constexpr friend ::tools::int_mod<P> operator+(
      const ::tools::int_mod<P>& lhs, const ::tools::int_mod<P>& rhs) {
    return ::tools::int_mod<P>(
        ::tools::int_mod<P>::add_impl(lhs.m_value, rhs.m_value));
  }
  ::tools::int_mod<P>& operator+=(const ::tools::int_mod<P>& other) {
    this->m_value = ::tools::int_mod<P>::add_impl(this->m_value, other.m_value);
    return *this;
  }
  ::tools::int_mod<P>& operator++() {
    this->m_value = ::tools::int_mod<P>::add_impl(this->m_value, 1u);
    return *this;
  }
  ::tools::int_mod<P> operator++(int) {
    ::tools::int_mod<P> prev(*this);
    ++this;
    return prev;
  }
  constexpr friend ::tools::int_mod<P> operator-(
      const ::tools::int_mod<P>& lhs, const ::tools::int_mod<P>& rhs) {
    return ::tools::int_mod<P>(
        ::tools::int_mod<P>::sub_impl(lhs.m_value, rhs.m_value));
  }
  ::tools::int_mod<P>& operator-=(const ::tools::int_mod<P>& other) {
    this->m_value = ::tools::int_mod<P>::sub_impl(this->m_value, other.m_value);
    return *this;
  }
  ::tools::int_mod<P>& operator--() {
    this->m_value = ::tools::int_mod<P>::sub_impl(this->m_value, 1u);
    return *this;
  }
  ::tools::int_mod<P> operator--(int) {
    ::tools::int_mod<P> prev(*this);
    --this;
    return prev;
  }
  constexpr friend ::tools::int_mod<P> operator*(
      const ::tools::int_mod<P>& lhs, const ::tools::int_mod<P>& rhs) {
    return ::tools::int_mod<P>(
        ::tools::int_mod<P>::mul_impl(lhs.m_value, rhs.m_value));
  }
  ::tools::int_mod<P>& operator*=(const ::tools::int_mod<P>& other) {
    this->m_value = ::tools::int_mod<P>::mul_impl(this->m_value, other.m_value);
    return *this;
  }
  template <::std::uint_fast32_t SFINAE_P = P,
            typename ::std::enable_if<::tools::is_prime(SFINAE_P),
                                      ::std::nullptr_t>::type = nullptr>
  constexpr ::tools::int_mod<P> inv() const {
    return this->m_value > 0u
               ? ::tools::int_mod<P>(
                     ::tools::extgcd<::std::int_fast64_t>(P, this->m_value).y0)
               : (throw ::std::invalid_argument("cannot divide by zero"));
  }
  template <::std::uint_fast32_t SFINAE_P = P,
            typename ::std::enable_if<!::tools::is_prime(SFINAE_P),
                                      ::std::nullptr_t>::type = nullptr>
  constexpr ::tools::int_mod<P> pow(const ::std::int_fast32_t exponent) const {
    return exponent >= 0
               ? this->pow_impl(static_cast<::std::uint_fast32_t>(exponent))
               : (throw ::std::invalid_argument(
                     "exponent must be non-negative"));
  }
  template <::std::uint_fast32_t SFINAE_P = P,
            typename ::std::enable_if<::tools::is_prime(SFINAE_P),
                                      ::std::nullptr_t>::type = nullptr>
  constexpr ::tools::int_mod<P> pow(const ::std::int_fast32_t exponent) const {
    return exponent >= 0
               ? this->pow_impl(static_cast<::std::uint_fast32_t>(exponent))
               : this->pow_impl(static_cast<::std::uint_fast32_t>(-exponent))
                     .inv();
  }
  template <::std::uint_fast32_t SFINAE_P = P,
            typename ::std::enable_if<::tools::is_prime(SFINAE_P),
                                      ::std::nullptr_t>::type = nullptr>
  constexpr friend ::tools::int_mod<P> operator/(
      const ::tools::int_mod<P>& lhs, const ::tools::int_mod<P>& rhs) {
    return lhs * rhs.inv();
  }
  template <::std::uint_fast32_t SFINAE_P = P,
            typename ::std::enable_if<::tools::is_prime(SFINAE_P),
                                      ::std::nullptr_t>::type = nullptr>
  ::tools::int_mod<P>& operator/=(const ::tools::int_mod<P>& other) {
    this->m_value =
        ::tools::int_mod<P>::mul_impl(this->m_value, other.inv().m_value);
    return *this;
  }
  friend ::std::istream& operator>>(::std::istream& is,
                                    ::tools::int_mod<P>& self) {
    return is >> self.m_value;
  }
  friend ::std::ostream& operator<<(::std::ostream& os,
                                    const ::tools::int_mod<P>& self) {
    return os << self.m_value;
  }
};
}  // namespace tools
namespace std {
template <::std::uint_fast32_t P>
struct hash<::tools::int_mod<P>> {
  using result_type = ::std::size_t;
  using argument_type = ::tools::int_mod<P>;
  ::std::size_t operator()(const argument_type& key) const {
    static const ::std::hash<::std::uint_fast32_t> hasher;
    return hasher(static_cast<::std::uint_fast32_t>(key));
  }
};
}  // namespace std
constexpr ::std::uint_fast32_t P = 1000000007;
int main() {
  ::std::int_fast64_t N;
  std::cin >> N;
  std::vector<tools::vector2<::std::int_fast64_t>> sardines;
  tools::read(sardines, N);
  {
    const auto it = std::remove(sardines.begin(), sardines.end(),
                                tools::vector2<::std::int_fast64_t>(0, 0));
    N -= std::distance(it, sardines.end());
    sardines.erase(it, sardines.end());
  }
  const auto regularize =
      [&](const tools::vector2<::std::int_fast64_t>& sardine) {
        return sardine.y < 0 || (sardine.y == 0 && sardine.x < 0) ? -sardine
                                                                  : sardine;
      };
  for (tools::vector2<::std::int_fast64_t>& sardine : sardines) {
    sardine = regularize(sardine / tools::gcd(sardine.x, sardine.y));
  }
  std::vector<tools::int_mod<P>> pow2(N + 1);
  pow2[0] = tools::int_mod<P>(1);
  for (::std::int_fast64_t i = 0; i < N; ++i) {
    pow2[i + 1] = pow2[i] * tools::int_mod<P>(2);
  }
  std::unordered_map<tools::vector2<::std::int_fast64_t>, ::std::int_fast64_t>
      tally;
  for (tools::vector2<::std::int_fast64_t>& sardine : sardines) {
    ++tally[sardine];
    tally.emplace(
        regularize(tools::vector2<::std::int_fast64_t>(-sardine.y, sardine.x)),
        0);
  }
  std::vector<tools::int_mod<P>> base;
  for (const std::pair<tools::vector2<::std::int_fast64_t>,
                       ::std::int_fast64_t>& pair : tally) {
    if (pair.first.x > 0) {
      base.push_back(pow2[pair.second] +
                     pow2[tally.at(tools::vector2<::std::int_fast64_t>(
                         -pair.first.y, pair.first.x))] -
                     tools::int_mod<P>(1));
    }
  }
  const auto cumsum = tools::cumsum1d(
      tools::monoid<tools::int_mod<P>>(std::multiplies<tools::int_mod<P>>(),
                                       tools::int_mod<P>(1)),
      base.begin(), base.end());
  tools::int_mod<P> answer(0);
  for (::std::int_fast64_t i = 0;
       i < static_cast<::std::int_fast64_t>(base.size()); ++i) {
    answer += (base[i] - tools::int_mod<P>(1)) * cumsum(i + 1, base.size());
  }
  std::cout << answer << std::endl;
  return 0;
}
