### Модульная арифметика

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long ll
#define all(x) begin(x), end(x)

const int N = 1.1e5;
const int MOD = 1e9 + 7;

int add(int a, int b) {
    return (a + b) % MOD;
}

int mul(long a, long b) {
    return (int)(a * b % MOD);
}

int power_mod(int a, int p) {
    int x = 1;
    for (; p > 0; p /= 2) {
        if (p % 2) {
            x = mul(x, a);
        }
        a = mul(a, a);
    }
    return x;
}

int divide(int a, int b) {
    return mul(a, power_mod(b, MOD - 2));
}

int fac[N], inv[N];

void precalc_factorials() {
    fac[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = mul(i, fac[i - 1]);
    }
    inv[N - 1] = divide(1, fac[N - 1]);
    for (int i = N - 2; i >= 0; --i) {
        inv[i] = mul(inv[i + 1], i + 1);
    }
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}