#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
#pragma warning(disable : 4996)
#pragma hdrstop
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T>
constexpr auto has_begin(int) -> decltype(std::begin(std::declval<T>()), true) {
  return true;
}
template <typename T>
constexpr bool has_begin(...) {
  return false;
}
template <typename T>
using is_container = std::integral_constant<bool, has_begin<T>(0)>;
template <typename T, typename... Types>
using is_one_of = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using is_sane_integer = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !is_one_of<typename std::remove_cv<T>::type, char, signed char,
                   unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
std::string to_string(const std::string& s) { return '"' + s + '"'; }
std::string to_string(const char* s) { return to_string(std::string(s)); }
std::string to_string(const char ch) { return {'\'', ch, '\''}; }
std::string to_string(const bool b) { return (b ? "true" : "false"); }
template <typename T,
          typename std::enable_if<Disjunction<
              is_sane_integer<T>::value,
              std::is_floating_point<T>::value>::value>::type* = nullptr>
std::string to_string(const T value) {
  return std::to_string(value);
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>&);
template <typename T,
          typename std::enable_if<is_container<T>::value>::type* = nullptr>
std::string to_string(const T& container) {
  bool is_first = true;
  std::string res = "{";
  for (const auto& x : container) {
    if (!is_first) {
      res += ", ";
    }
    is_first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>& p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
std::vector<std::string> vec_splitter(std::string s) {
  s += ',';
  std::vector<std::string> res;
  while (!s.empty()) {
    const size_t pos = s.find(',');
    res.emplace_back(s.substr(0, pos));
    s = s.substr(pos + 1);
  }
  return res;
}
void debug_out(std::vector<std::string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  std::cerr << std::endl;
}
template <typename Head, typename... Tail>
void debug_out(std::vector<std::string> args, int idx, int LINE_NUM, Head H,
               Tail... T) {
  std::stringstream ss;
  ss << to_string(H);
  if (idx > 0) {
    std::cerr << ", ";
  } else {
    std::cerr << "Line(" << LINE_NUM << ") ";
  }
  const std::string& arg = args[idx];
  const std::string value = ss.str();
  if (arg == value) {
    std::cerr << arg;
  } else {
    std::cerr << arg << " = " << value;
  }
  debug_out(args, idx + 1, LINE_NUM, T...);
}
namespace std {
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
  for (auto& it : vec) {
    in >> it;
  }
  return in;
}
template <typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& rhs) {
  in >> rhs.first >> rhs.second;
  return in;
}
}  // namespace std
void assign_files_input_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  using value_type = T;
  constexpr explicit IntegerIterator(const value_type value) : value_(value) {}
  IntegerIterator& operator++() {
    ++value_;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value_;
    return copy;
  }
  IntegerIterator& operator--() {
    --value_;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value_;
    return copy;
  }
  constexpr value_type operator*() const { return value_; }
  constexpr bool operator==(const IntegerIterator rhs) const {
    return value_ == rhs.value_;
  }
  constexpr bool operator!=(const IntegerIterator rhs) const {
    return !(*this == rhs);
  }
  constexpr value_type operator+(const IntegerIterator rhs) const {
    return value_ + rhs.value_;
  }
  IntegerIterator& operator+=(const IntegerIterator rhs) const {
    value_ += rhs.value_;
    return *this;
  }
  constexpr value_type operator-(const IntegerIterator rhs) const {
    return value_ - rhs.value_;
  }
  IntegerIterator& operator-=(const IntegerIterator rhs) const {
    value_ -= rhs.value_;
    return *this;
  }

 private:
  value_type value_;
};
template <typename T>
class IntegerRange {
 public:
  using const_iterator = IntegerIterator<T>;
  constexpr IntegerRange(const T begin, const T end)
      : begin_(begin), end_(end) {}
  constexpr const_iterator begin() const { return const_iterator(begin_); }
  constexpr const_iterator end() const { return const_iterator(end_); }
  constexpr T size() const { return end_ - begin_; }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedRange {
 public:
  using const_iterator = typename std::decay<T>::type::const_iterator;
  using reverse_iterator = std::reverse_iterator<const_iterator>;
  explicit constexpr ReversedRange(const T& iterable)
      : begin_(iterable.begin()), end_(iterable.end()) {}
  constexpr reverse_iterator begin() const { return reverse_iterator(end_); }
  constexpr reverse_iterator end() const { return reverse_iterator(begin_); }

 private:
  const_iterator begin_;
  const_iterator end_;
};
template <typename T>
ReversedRange<T> reversed(T&& iterable) {
  return ReversedRange<T>{iterable};
}
template <typename T>
constexpr IntegerRange<T> range(const T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
constexpr IntegerRange<T> range(const T from, const T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T from, const T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from) {
  return reversed(range(from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from, const T to) {
  return reversed(range(to, from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from) {
  return reversed(range(from + 1));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from,
                                                            const T to) {
  return reversed(range(to, from + 1));
}
template <typename R>
void sort(R& range) {
  std::sort(range.begin(), range.end());
}
template <typename R, typename Comp>
void sort(R& range, Comp comp) {
  std::sort(range.begin(), range.end(), comp);
}
template <typename R>
void reverse(R& range) {
  std::reverse(range.begin(), range.end());
}
template <typename R, typename T>
auto lower_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto lower_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value, comp);
}
template <typename R, typename T>
auto upper_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto upper_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value, comp);
}
template <typename R>
auto min_element(const R& range) -> decltype(range.begin()) {
  return std::min_element(range.begin(), range.end());
}
template <typename R>
auto max_element(const R& range) -> decltype(range.begin()) {
  return std::max_element(range.begin(), range.end());
}
template <typename R>
bool next_permutation(R& range) {
  return std::next_permutation(range.begin(), range.end());
}
template <typename T>
void unique(std::vector<T>& range) {
  range.erase(std::unique(range.begin(), range.end()), range.end());
}
template <typename T>
void dedup(std::vector<T>& range) {
  sort(range);
  unique(range);
}
template <typename R>
R sorted(R range) {
  sort(range);
  return range;
}
template <typename R, typename Comp>
R sorted(R range, Comp comp) {
  sort(range, comp);
  return range;
}
static constexpr long double PI = 3.14159265358979323846;
static constexpr long double EPS = 1e-9;
static constexpr int32_t INF = 0x3f3f3f3f;
static constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr int32_t DX[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
static constexpr int32_t DY[8] = {0, 1, 0, -1, -1, 1, 1, -1};
enum Direction : uint8_t {
  Up,
  Right,
  Down,
  Left,
  UpLeft,
  UpRight,
  DownRight,
  DownLeft,
  North = Up,
  East = Right,
  South = Down,
  West = Left,
  NorthWest = UpLeft,
  NorthEast = UpRight,
  SouthEast = DownRight,
  SouthWest = DownLeft,
  Unknown = 255
};
namespace Random {
inline std::chrono::system_clock::rep current_timestamp() {
  return std::chrono::system_clock::now().time_since_epoch().count();
}
inline uint64_t get_new_rand_seed() {
  return static_cast<uint64_t>(current_timestamp());
}
inline uint64_t get_rand_seed() {
  static const uint64_t kRandSeed = get_new_rand_seed();
  return kRandSeed;
}
using Engine = std::mt19937_64;
template <typename T>
using Distribution = std::uniform_int_distribution<T>;
inline Engine& random_engine() {
  static Engine engine(get_rand_seed());
  return engine;
}
template <typename T>
inline T get(const T to) {
  Distribution<T> distribution(0, to);
  return distribution(random_engine());
}
template <typename T>
inline T get(const T from, const T to) {
  return get(to - from) + from;
}
template <typename T = int32_t>
inline T get() {
  return get(static_cast<T>(0), std::numeric_limits<T>::max());
}
}  // namespace Random
template <typename T,
          typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
class SafeIntegralHash {
 public:
  const T kRandomValue = static_cast<T>(Random::current_timestamp());
  T operator()(const T& value) const { return value ^ kRandomValue; }
};
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMap = std::unordered_map<Key, Value, SafeIntegralHash<Key>>;
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiMap =
    std::unordered_multimap<Key, Value, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedSet = std::unordered_set<Key, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiSet =
    std::unordered_multiset<Key, SafeIntegralHash<Key>>;
namespace std {
template <typename T, typename U>
struct hash<std::pair<T, U>> {
  std::size_t operator()(const std::pair<T, U>& pair) const {
    return pair.first * 877117 + pair.second;
  }
};
}  // namespace std
template <typename T>
inline bool umin(T& a, const T& b) {
  return (b < a ? a = b, true : false);
}
template <typename T>
inline bool umax(T& a, const T& b) {
  return (a < b ? a = b, true : false);
}
template <typename T, size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
template <typename T, typename U,
          typename std::enable_if<is_container<T>::value &&
                                  is_container<U>::value>::type* = nullptr>
T as_container(const U& collection) {
  return T{std::begin(collection), std::end(collection)};
}
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pli = std::pair<ll, int>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vp = std::vector<pii>;
template <typename T>
inline T gcd(T a, T b) {
  while (b != 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
inline T lcm(const T& a, const T& b) {
  return a / gcd(a, b) * b;
}
template <typename T>
constexpr inline T sqr(const T& x) {
  return x * x;
}
template <typename T, typename U>
inline T binpow(T a, U b) {
  static_assert(std::is_integral<U>::value,
                "Degree must be integral. For real degree use pow().");
  T ret = 1;
  while (b != 0) {
    if ((b & 1) != 0) {
      ret *= a;
    }
    a *= a;
    b >>= 1;
  }
  return ret;
}
inline uint32_t abs(const uint32_t x) { return x; }
inline uint64_t abs(const uint64_t x) { return x; }
template <typename T>
T factorial(const size_t n) {
  T ret = 1;
  for (size_t i = 2; i <= n; ++i) {
    ret *= i;
  }
  return ret;
}
template <typename T>
void binomial_coefficients(const size_t n, std::vector<std::vector<T>>* c) {
  std::vector<std::vector<T>> result(n, std::vector<T>(n));
  for (size_t i = 0; i < n; ++i) {
    result[i][0] = 1;
    result[i][i] = 1;
    for (size_t j = 1; j < i; ++j) {
      result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
    }
  }
  c->swap(result);
}
template <typename T>
std::vector<T> calc_powers(const T base, const size_t n) {
  std::vector<T> powers(n + 1);
  powers[0] = 1;
  for (size_t i = 1; i < powers.size(); ++i) {
    powers[i] = powers[i - 1] * base;
  }
  return powers;
}
template <typename T>
std::vector<T> calc_factorial(const size_t n) {
  std::vector<T> factorial(n + 1);
  factorial[0] = 1;
  for (size_t i = 1; i < factorial.size(); ++i) {
    factorial[i] = factorial[i - 1] * i;
  }
  return factorial;
}
template <typename T>
inline bool is_prime(const T& n) {
  if (n < 2) {
    return false;
  }
  const T floored_square_root = static_cast<T>(sqrt(n));
  for (T i = 2; i <= floored_square_root; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
template <typename T>
inline T next_prime(const T& n) {
  for (T candidate = n;; ++candidate) {
    if (is_prime(candidate)) {
      return candidate;
    }
  }
}
template <typename T>
inline T random_prime(const T from, const T to) {
  return next_prime(Random::get(from, to));
}
template <typename T = uint32_t>
inline T random_big_prime(const T from = 1000000000, const T to = INF) {
  return random_prime(from, to);
}
inline std::vector<bool> eratosthenes_sieve(const size_t n) {
  if (n < 2) {
    return std::vector<bool>(n, false);
  }
  std::vector<bool> prime(n, true);
  prime[0] = false;
  prime[1] = false;
  for (size_t i = 4; i < n; i += 2) {
    prime[i] = false;
  }
  for (size_t i = 3; i * i < n; i += 2) {
    if (prime[i]) {
      const size_t delta = i * 2;
      for (size_t j = i * i; j < n; j += delta) {
        prime[j] = false;
      }
    }
  }
  return prime;
}
template <typename T = uint32_t>
inline std::vector<T> primes_vector(const size_t n) {
  if (n < 2) {
    return {};
  }
  const std::vector<bool> prime = eratosthenes_sieve(n);
  std::vector<T> result = {2};
  for (size_t i = 3; i < n; i += 2) {
    if (prime[i]) {
      result.emplace_back(i);
    }
  }
  return result;
}
template <typename T = uint32_t>
inline std::vector<T> min_prime_div_vector(const size_t n) {
  std::vector<T> result(n, 0);
  result[0] = 1;
  result[1] = 1;
  for (size_t i = 2; i < n; i += 2) {
    result[i] = 2;
  }
  size_t index = 3;
  while (index * index < n) {
    if (result[index] == 0) {
      result[index] = index;
      const size_t delta = index * 2;
      for (size_t j = index * index; j < n; j += delta) {
        if (result[j] == 0) {
          result[j] = index;
        }
      }
    }
    index += 2;
  }
  while (index < n) {
    if (result[index] == 0) {
      result[index] = index;
    }
    ++index;
  }
  return result;
}
template <typename T, typename size_type = std::size_t>
std::vector<std::pair<T, size_type>> get_prime_divisors_vector(
    const T n, const std::vector<T>& min_prime_div_vector) {
  std::vector<std::pair<T, size_type>> prime_divisors;
  T cur = n;
  while (cur > 1) {
    const T min_div = min_prime_div_vector[cur];
    if (!prime_divisors.empty() && prime_divisors.back().first == min_div) {
      ++prime_divisors.back().second;
    } else {
      prime_divisors.emplace_back(min_div, 1);
    }
    cur /= min_div;
  }
  return prime_divisors;
}
template <typename T, typename size_type = std::size_t>
std::vector<std::pair<T, size_type>> get_prime_divisors_vector(const T n) {
  std::vector<std::pair<T, size_type>> prime_divisors;
  T cur = n;
  for (T i = 2; static_cast<int64_t>(i) * i <= cur; ++i) {
    if (cur % i == 0) {
      size_type degree = 0;
      while (cur % i == 0) {
        ++degree;
        cur /= i;
      }
      prime_divisors.emplace_back(i, degree);
    }
  }
  if (cur > 1) {
    prime_divisors.emplace_back(cur, 1);
  }
  return prime_divisors;
}
template <typename T>
T euler_function(T n) {
  T res = n;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      res -= res / i;
    }
  }
  if (n > 1) {
    res -= res / n;
  }
  return res;
}
constexpr const int kBaseModulo = 1000000007;
template <typename T>
inline T& add_mod(T& a, const T b, const T mod = kBaseModulo) {
  if ((a += b) >= mod) {
    a -= mod;
  }
  return a;
}
template <typename T>
inline T& sub_mod(T& a, const T b, const T mod = kBaseModulo) {
  if ((a -= b) < 0) {
    a += mod;
  }
  return a;
}
template <typename T>
inline T& mul_mod(T& a, const T b, const T mod = kBaseModulo) {
  a = static_cast<int64_t>(a) * b % mod;
  return a;
}
template <typename T, typename U, typename Q>
inline T binpow(T a, U b, Q mod) {
  static_assert(std::is_integral<U>::value,
                "Degree must be integral. For real degree use pow().");
  int64_t ret = 1;
  a %= mod;
  while (b != 0) {
    if ((b & 1) != 0) {
      ret = ret * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return ret % mod;
}
template <typename T, typename U>
T inverse_element(const T n, const U mod) {
  return binpow(static_cast<int64_t>(n), mod - 2, mod);
}
template <typename T, typename U>
std::vector<T> inverse_element_for_segment(const size_t n, const U mod) {
  std::vector<T> res(n + 1);
  res[1] = 1;
  for (size_t i = 2; i < res.size(); ++i) {
    res[i] = (mod - static_cast<int64_t>(mod) / i * res[mod % i] % mod) % mod;
  }
  return res;
}
template <typename T>
T inverse_element_comp_mod(const T n, const T mod) {
  return binpow(n, euler_function(mod) - 1, mod);
}
template <typename T, typename U>
std::vector<T> calc_inverse_factorial(const size_t n, const U mod) {
  const std::vector<T> inv = inverse_element_for_segment<T>(n, mod);
  std::vector<T> inversed_factorial(n + 1);
  inversed_factorial[0] = 1;
  inversed_factorial[1] = 1;
  for (size_t i = 2; i < inversed_factorial.size(); ++i) {
    inversed_factorial[i] = inversed_factorial[i - 1];
    mul_mod(inversed_factorial[i], inv[i], mod);
  }
  return inversed_factorial;
}
template <typename T, T MOD = kBaseModulo>
class ModInt {
 public:
  using value_type = T;
  static constexpr value_type Modulo = MOD;
  constexpr ModInt() : ModInt(0) {}
  constexpr ModInt(const value_type value) : value_(value) {
    static_assert(MOD > 0, "Modulo must be strictly positive.");
  }
  template <typename U>
  constexpr static ModInt from_integer(const U value) {
    return {ModInt::normalize(value)};
  }
  constexpr value_type value() const { return value_; }
  constexpr value_type mod() const { return MOD; }
  constexpr bool operator==(const ModInt rhs) const {
    return value_ == rhs.value_;
  }
  constexpr bool operator!=(const ModInt rhs) const { return !operator==(rhs); }
  constexpr bool operator<(const ModInt& rhs) const {
    return value_ < rhs.value_;
  }
  constexpr bool operator>(const ModInt& rhs) const {
    return value_ > rhs.value_;
  }
  ModInt operator+(const ModInt rhs) const {
    value_type x = value_;
    return {add_mod(x, rhs.value_, MOD)};
  }
  ModInt operator-(const ModInt rhs) const {
    value_type x = value_;
    return {sub_mod(x, rhs.value_, MOD)};
  }
  ModInt operator*(const ModInt rhs) const {
    value_type x = value_;
    return {mul_mod(x, rhs.value_, MOD)};
  }
  ModInt& operator+=(const ModInt rhs) {
    add_mod(value_, rhs.value_, MOD);
    return *this;
  }
  ModInt& operator-=(const ModInt rhs) {
    sub_mod(value_, rhs.value_, MOD);
    return *this;
  }
  ModInt& operator*=(const ModInt rhs) {
    mul_mod(value_, rhs.value_, MOD);
    return *this;
  }
  ModInt operator++(int) {
    const ModInt ret(value_);
    add_mod(value_, static_cast<value_type>(1), MOD);
    return ret;
  }
  ModInt operator--(int) {
    const ModInt ret(value_);
    sub_mod(value_, static_cast<value_type>(1), MOD);
    return ret;
  }
  ModInt& operator++() {
    add_mod(value_, static_cast<value_type>(1), MOD);
    return *this;
  }
  ModInt& operator--() {
    sub_mod(value_, static_cast<value_type>(1), MOD);
    return *this;
  }
  constexpr ModInt operator+() const { return {value_}; }
  constexpr ModInt operator-() const { return negate(); }
  constexpr ModInt negate() const { return {ModInt::normalize(-value_)}; }
  constexpr ModInt inverse() const { return {inverse_element(value_, MOD)}; }
  std::string str() const { return std::to_string(value_); }
  template <typename C>
  C as() const {
    return static_cast<C>(value_);
  }
  explicit operator int() const { return as<int32_t>(); }
  explicit operator long long() const { return as<int64_t>(); }
  friend std::istream& operator>>(std::istream& in, ModInt& rhs) {
    value_type x;
    in >> x;
    rhs.value_ = ModInt::normalize(x);
    return in;
  }
  friend std::ostream& operator<<(std::ostream& out, const ModInt& rhs) {
    out << rhs.value_;
    return out;
  }

 private:
  value_type value_;
  template <typename U>
  static value_type normalize(const U value) {
    if (value >= 0 && value < MOD) {
      return value;
    }
    const value_type ret = value % MOD;
    if (ret < 0) {
      return ret + MOD;
    }
    return ret;
  }
};
namespace std {
template <typename T, T MOD>
struct is_integral<ModInt<T, MOD>> : std::true_type {};
template <typename T, T MOD>
struct is_arithmetic<ModInt<T, MOD>> : std::true_type {};
}  // namespace std
template <typename T, T MOD>
std::string to_string(const ModInt<T, MOD>& val) {
  return val.str();
}
class EPutiPoDelitelyam {
 public:
  static constexpr bool kWriteCaseNumber = false;
  static constexpr bool kMultiTest = false;
  const int kMaxn = 31666666;
  const int kMaxPrimes = 60;
  using Int = ModInt<int, 998244353>;
  using PrimesVector = std::vector<std::pair<ll, size_t>>;
  void solve(std::istream& in, std::ostream& out) {
    ll n;
    int q;
    in >> n >> q;
    PrimesVector prime_divisors;
    ll tmp = n;
    for (ll x : primes) {
      int cnt = 0;
      while (tmp % x == 0) {
        tmp /= x;
        ++cnt;
      }
      if (cnt > 0) {
        prime_divisors.emplace_back(x, cnt);
      }
    }
    if (tmp > 1) {
      prime_divisors.emplace_back(tmp, 1);
    }
    auto calc = [&prime_divisors, this, &n](const ll div) {
      42;
      PrimesVector prime_divs;
      if (div >= kMaxn) {
        const auto vec = get_prime_divisors_vector<int>(n / div, min_prime_div);
        prime_divs = prime_divisors;
        int index = 0;
        for (const auto& it : vec) {
          while (prime_divs[index].first < it.first) {
            ++index;
          }
          prime_divs[index].second -= it.second;
        }
      } else {
        prime_divs = as_container<PrimesVector>(
            get_prime_divisors_vector<int>(div, min_prime_div));
      }
      Int ans = 1;
      int total = 0;
      for (const auto& it : prime_divs) {
        ans *= inversed_factorial[it.second];
        total += it.second;
      }
      ans *= factorial[total];
      return ans;
    };
    for (int _ : range(q)) {
      ll x, y;
      in >> x >> y;
      const ll g = gcd(x, y);
      const Int ans = calc(x / g) * calc(y / g);
      out << ans << "\n";
    }
    out << std::endl;
  }
  std::vector<Int> factorial;
  std::vector<Int> inversed_factorial;
  std::vector<int> primes;
  std::vector<int> min_prime_div;
  EPutiPoDelitelyam() {
    factorial = calc_factorial<Int>(kMaxPrimes);
    inversed_factorial = as_container<std::vector<Int>>(
        calc_inverse_factorial<int>(kMaxPrimes, Int::Modulo));
    min_prime_div = min_prime_div_vector<int>(kMaxn);
    primes = primes_vector<int>(kMaxn);
  }
  static constexpr bool kUseCustomChecker = false;
  bool check(std::istringstream in, std::istringstream jury,
             std::istringstream out) {
    return true;
  }
  static constexpr size_t kGeneratedTestsCount = 0;
  static constexpr bool kStopAfterFirstFail = false;
  static void generate_test(std::ostream& test) {}
};
int main() {
  EPutiPoDelitelyam solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  srand(time(nullptr));
  out << std::fixed << std::setprecision(16);
  if (EPutiPoDelitelyam::kMultiTest) {
    size_t tests_count;
    in >> tests_count;
    for (size_t test_id : inclusiveRange<size_t>(1, tests_count)) {
      if (EPutiPoDelitelyam::kWriteCaseNumber) {
        out << "Case #" << test_id << ": ";
      }
      solver.solve(in, out);
    }
  } else {
    solver.solve(in, out);
  }
  return 0;
}
