1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17

constexpr ll MOD = 1e9+7;

inline ll pw(ll base, ll exp) {
	ll res = 1;
	while (exp) {
		if (exp & 1) (res *= base) %= MOD;
		exp >>= 1, (base *= base) %= MOD;
	}
	return res;
}
inline ll inv(ll x) { return pw(x, MOD-2); }

ll fact[MX] = { 1 }, ifact[MX] = { 1 };
inline ll nCr(int n, int k) { return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }


for (int i = 1; i < N; ++i) fact[i] = i*fact[i-1]%MOD, ifact[i] = inv(fact[i]);