#include <algorithm>
#include <array>
#include <bits/stdc++.h>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <vector>

// lib/quo.hpp
#ifndef QUO_H
#define QUO_H

/*
a == tools::quo(a, b) * b + tools::mod(a, b)
0 <= tools::mod(a, b) < std::abs(b)
*/

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;
  }
}

#endif

// lib/is_prime.hpp
#ifndef IS_PRIME_H
#define IS_PRIME_H


/*
usage:

static_assert(tools::is_prime(P), "P must be prime.");
*/

// Source: Stack Overflow ( https://stackoverflow.com/questions/18303632/compile-time-prime-checking/18306693#18306693 )
// Author: Casey ( https://stackoverflow.com/users/923854/casey )
// License: CC BY-SA 3.0
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;
      }

      // precondition: low*low <= n, high*high > n.
      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));
      }

      // returns ceiling(sqrt(n))
      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));
      }

      // returns true if n is divisible by an odd integer in
      // [2 * low + 1, 2 * high + 1).
      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));
      }
    }
  }

  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))));
  }
}

#endif

// lib/rotate_left.hpp
#ifndef ROTATE_LEFT_HPP
#define ROTATE_LEFT_HPP


/*
usage:

// 5-bit circular shift to the left
tools::rotate_left(x, 5);
*/

// Source: Stack Overflow ( https://stackoverflow.com/questions/776508/best-practices-for-circular-shift-rotate-operations-in-c/776523#776523 )
// Author: John Regehr ( https://blog.regehr.org/ ) and Peter Cordes ( https://stackoverflow.com/users/224132/peter-cordes )
// License: CC BY-SA 3.0
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) + "."));
  }
}

#endif

// lib/monoid.hpp
#ifndef MONOID_HPP
#define MONOID_HPP


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);
    }
  };
}

#endif

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

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);
  }
}

#endif

// lib/mod.hpp
#ifndef MOD_HPP
#define MOD_HPP


/*
a == tools::quo(a, b) * b + tools::mod(a, b)
0 <= tools::mod(a, b) < std::abs(b)
*/

namespace tools {
  template <typename T>
  constexpr T mod(const T& lhs, const T& rhs) {
    return lhs - ::tools::quo(lhs, rhs) * rhs;
  }
}

#endif

// lib/extgcd.hpp
#ifndef EXTGCD_HPP
#define EXTGCD_HPP


/*
usage:

const auto result = tools::extgcd(a, b);

// 0を単位元として追加したGCD
int gcd = result.gcd;

// a * x + b * y = gcd を満たす、無数にある(x, y)の組のうちの一つ
int x0 = result.x0;
int y0 = result.y0;
*/

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) {
        }
      };
    }
  }
  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);
  }
}

#endif

// lib/vector2.hpp
#ifndef VECTOR2_HPP
#define VECTOR2_HPP


/*
usage:

tools::vector2<int>(6, 5) // => (6, 5)
*/

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 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;
  }
}

#endif

// lib/square.hpp
#ifndef SQUARE_HPP
#define SQUARE_HPP


/*
usage:

tools::square(5) => 25
*/

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);
  }
}

#endif

// lib/group.hpp
#ifndef GROUP_HPP
#define GROUP_HPP


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>());
    }
  };
}

#endif

// lib/gcd.hpp
#ifndef GCD_HPP
#define GCD_HPP


/*
usage:

tools::gcd(4, 5);
*/

namespace tools {
  template <typename T>
  T gcd(const T& a, const T& b) {
    return ::tools::extgcd(a, b).gcd;
  }
}

#endif

// lib/pow.hpp
#ifndef POW_H
#define POW_H


/*
usage:

tools::pow(tools::monoid<int>::multiplies(), 2, 5) => 32
*/

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);
  }
}

#endif

// lib/cumsum.hpp
#ifndef CUMSUM_HPP
#define CUMSUM_HPP


/*
usage:

// 元配列はa[y][x]の形で値が格納されているとする
std::vector<std::vector<int>> a;
const auto cumsum = tools::cumsum2d(tools::group<int>::plus(), a.begin(), a.end());
cumsum(x1, y1, x2, y2);
*/

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]);
        }
      };
    }
  }

  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);
  }
}

#endif

// lib/int_mod.hpp
#ifndef INT_MOD_HPP
#define INT_MOD_HPP


/*
usage:

constexpr const std::uint_fast32_t p = 3;
tools::int_mod<p>(5) + tools::int_mod<p>(4) // => 0
*/

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 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));
    }
  };
}

#endif

// main.cpp

constexpr u32 P = 1000000007;

int main() {
  i64 N;
  std::cin >> N;
  std::vector<tools::vector2<i64>> sardines;
  tools::read(sardines, N);

  tools::int_mod<P> answer(0);
  {
    const auto it = std::remove(sardines.begin(), sardines.end(), tools::vector2<i64>(0, 0));
    N -= std::distance(it, sardines.end());
    answer += tools::int_mod<P>(std::distance(it, sardines.end()));
    sardines.erase(it, sardines.end());
  }
  const auto regularize = [&](const tools::vector2<i64>& sardine) {
    return sardine.y < 0 || (sardine.y == 0 && sardine.x < 0) ? -sardine : sardine;
  };
  for (tools::vector2<i64>& 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 (i64 i = 0; i < N; ++i) {
    pow2[i + 1] = pow2[i] * tools::int_mod<P>(2);
  }

  std::unordered_map<tools::vector2<i64>, i64> tally;
  for (tools::vector2<i64>& sardine : sardines) {
    ++tally[sardine];
    tally.emplace(regularize(tools::vector2<i64>(-sardine.y, sardine.x)), 0);
  }

  std::vector<tools::int_mod<P>> base;
  for (const std::pair<tools::vector2<i64>, i64>& pair : tally) {
    if (pair.first.x > 0) {
      base.push_back(pow2[pair.second] + pow2[tally.at(tools::vector2<i64>(-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()
  );

  for (i64 i = 0; i < static_cast<i64>(base.size()); ++i) {
    answer += (base[i] - tools::int_mod<P>(1)) * cumsum(i + 1, base.size());
  }

  std::cout << answer << std::endl;
  return 0;
}

Measured memory_bytes: 37036