//Matrix
#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
using i64 = long long;
const i64 mod  = 1000000000000007LL;
#include<bits/stdc++.h>
using namespace std;
struct Mat {
  int n, m;
  vector<vector<i64 >> a;
  Mat() { }
  Mat(int _n, int _m) {n = _n; m = _m; a.assign(n, vector<i64 >(m, 0)); }
  Mat(vector< vector<i64 > > v) { n = v.size(); m = n ? v[0].size() : 0; a = v; }
  inline void make_unit() {
    assert(n == m);
    for (int i = 0; i < n; i++)  {
      for (int j = 0; j < n; j++) a[i][j] = i == j;
    }
  }
  inline Mat operator + (const Mat &b) {
    assert(n == b.n && m == b.m);
    Mat ans = Mat(n, m);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        ans.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
        if (ans.a[i][j] < 0) ans.a[i][j] += mod;
      }
    }
    return ans;
  } 
  inline Mat operator - (const Mat &b) {
    assert(n == b.n && m == b.m);
    Mat ans = Mat(n, m);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        ans.a[i][j] = (a[i][j] - b.a[i][j] + mod) % mod;
      }
    }
    return ans;
  }
Mat operator*(const Mat& b) const {
    assert(m == b.n);
    Mat c(n, b.m);
    for (int i = 0; i < n; ++i) {
      for (int k = 0; k < m; ++k) if (a[i][k]) {
        i128 aik = a[i][k];
        for (int j = 0; j < b.m; ++j) if (b.a[k][j]) {
          c.a[i][j] = (c.a[i][j] + (i64)((aik * b.a[k][j]) % mod)) % mod;
        }
      }
    }
    return c;
  }
  inline Mat pow(long long k) {
    assert(n == m);
    Mat ans(n, n), t = *this; ans.make_unit();
    while (k) {
      if (k & 1) ans = ans * t;
      t = t * t;
      k >>= 1;
    }
    return ans;
  }
  inline Mat& operator += (const Mat& b) { return *this = (*this) + b; }
  inline Mat& operator -= (const Mat& b) { return *this = (*this) - b; }
  inline Mat& operator *= (const Mat& b) { return *this = (*this) * b; }
  inline bool operator == (const Mat& b) { return a == b.a; }
  inline bool operator != (const Mat& b) { return a != b.a; }
  inline vector<i64>& operator[](int i) {return a[i];} 
};

class DSU {
public:
    vector<int> parent, size;

    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]); 
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }

    int getSize(int x) {
        return size[find(x)];
    }
};

int phi(int n) {
    int res = n;
    for (int 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;
}
int modInv(int a, int m){ // giả sử a, m nguyên tố cùng nhau
    int p = phi(m); // hàm `phi(n)` tính phi hàm Euler của n
    int x = Pow(a, p - 1, m); // hàm `Pow(a, b, c)` tính a^b mod c
    return x;
}
int modInv(int a, int m){
    int x, y;
    d = extEuclid(a, m, x, y); // hàm euclid mở rộng ở bài Thuật toán Euclid
    if (d != 1) return -1; // không tồn tại nghịch đảo modulo
    x = (x % m + m) % m;
    return x; // nghịch đảo modulo
}
// Hàm trả về ƯCLN của a và b đồng thời thay đổi giá trị của x, y
int extEuclid(int a, int b, int& x, int& y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int q = a / b;
    int r = a - b * q;
    int x1 = 0, y1 = 0;
    int d = extEuclid(b, r, x1, y1);
    x = y1;
    y = x1 - q * y1;
    return d;
}

int binPow(int x, int y, int mod) {
    int ret = 0;
    for (; y; y /= 2, x = 1ll * x * x % mod) {
        if (y % 2) ret = 1ll * ret * x % mod;
    }
    return ret;
}

//Nghịch đảo modulo
int inv(int x, int mod) {
    return binPow(x, mod - 2, mod);
}

//Phép chia modulo
int divMod(int a, int b, int mod) {
    return 1ll * a * inv(b) % mod;
}