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

constexpr ll MOD = 1e9+7;

int pow(int base, int exp) {
	int res = 1;
	while (exp) {
		if (exp & 1) res = ((ll)base * res) % MOD;
		exp >>= 1;
		base = ((ll)base * base) % MOD;
	}
	return res;
}

int inv(int x) { return pow(x, MOD - 2); }