inline int qr(){
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void qw(int a) {
if(a < 0) putchar('-'), a = -a;
if(a > 9) qw(a / 10);
putchar((a % 10) ^ 48);
}
DEBUG
#define dbg(x) cerr << #x << "=" << x << '\n'
template<class t, class u>
ostream &operator<<(ostream &os, const pair<t, u> &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template<class t>
ostream &operator<<(ostream &os, const vector<t> &v) {
os << "[" << (*v.begin());
for (int i = 1;i < v.size();i++) os << ", " << v[i];
return os << "]";
}
Mint
constexpr int P = 1000000007;
using ll = long long;
// assume -P <= x < 2P
int norm(int x) {if(x < 0)x += P;if (x >= P)x -= P;return x;}
template<class T>T power(T a, int b){T res = 1;for (; b; b /= 2, a *= a)if (b & 1)res *= a;return res;}
struct Mint {
int x;Mint(int x = 0) : x(norm(x)){}
int val() const {return x;}
Mint operator-() const {return Mint(norm(P - x));}
Mint inv() const {assert(x != 0);return power(*this, P - 2);}
Mint &operator*=(const Mint &rhs) { x = ll(x) * rhs.x % P; return *this;}
Mint &operator+=(const Mint &rhs) { x = norm(x + rhs.x); return *this;}
Mint &operator-=(const Mint &rhs) { x = norm(x - rhs.x); return *this;}
Mint &operator/=(const Mint &rhs) {return *this *= rhs.inv();}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {Mint res = lhs; res *= rhs; return res;}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {Mint res = lhs; res += rhs; return res;}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {Mint res = lhs; res -= rhs; return res;}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {Mint res = lhs; res /= rhs; return res;}
};