// Mini-proyek Bagian 5: Penghitung Susunan -- versi selesai.
//
// Compile:  g++ -std=c++17 -O2 -o susunan projects/05-penghitung-susunan/finished.cpp
// Jalankan: ./susunan < projects/05-penghitung-susunan/contoh-masukan.txt
//
// Penguji menulis ke cerr, jadi keluaran yang dinilai tetap bersih.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const long long MOD = 1000000007;
const int MAKS = 1000005;
long long fakt[MAKS];

long long pangkat_mod(long long a, long long b, long long m) {
    long long hasil = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) hasil = hasil * a % m;
        a = a * a % m;
        b /= 2;
    }
    return hasil;
}

long long invers(long long a) {
    return pangkat_mod(a, MOD - 2, MOD);
}

long long permutasi(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fakt[n] * invers(fakt[n - r]) % MOD;
}

long long kombinasi(int n, int r) {
    if (r < 0 || r > n) return 0;
    long long bawah = fakt[r] * fakt[n - r] % MOD;
    return fakt[n] * invers(bawah) % MOD;
}

long long susunan_kata(const string &s) {
    int cacah[26] = {0};
    for (char c : s) cacah[c - 'A']++;

    long long hasil = fakt[s.size()];
    for (int i = 0; i < 26; i++)
        if (cacah[i] > 1) hasil = hasil * invers(fakt[cacah[i]]) % MOD;
    return hasil;
}

// --- penguji: pencacahan langsung untuk data kecil ---

long long cacah_kombinasi(int n, int r) {
    long long banyak = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int bit = 0;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) bit++;
        if (bit == r) banyak++;
    }
    return banyak;
}

long long cacah_susunan(string s) {
    sort(s.begin(), s.end());
    long long banyak = 0;
    do {
        banyak++;
    } while (next_permutation(s.begin(), s.end()));
    return banyak;
}

void jalankan_penguji() {
    for (int n = 0; n <= 8; n++)
        for (int r = 0; r <= n; r++)
            if (kombinasi(n, r) != cacah_kombinasi(n, r)) {
                cerr << "kombinasi berbeda pada n = " << n << ", r = " << r << "\n";
                return;
            }

    string uji[] = {"A", "AA", "AB", "AAB", "ABC", "AABB", "OSNOSN", "ABCDEFG"};
    for (const string &s : uji)
        if (susunan_kata(s) != cacah_susunan(s)) {
            cerr << "susunan berbeda pada kata " << s << "\n";
            return;
        }

    cerr << "penguji: rumus dan pencacahan langsung cocok\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fakt[0] = 1;
    for (int i = 1; i < MAKS; i++) fakt[i] = fakt[i - 1] * i % MOD;

    int q;
    cin >> q;

    while (q--) {
        int jenis;
        cin >> jenis;

        if (jenis == 1) {
            int n, r;
            cin >> n >> r;
            cout << permutasi(n, r) << "\n";
        } else if (jenis == 2) {
            int n, r;
            cin >> n >> r;
            cout << kombinasi(n, r) << "\n";
        } else if (jenis == 3) {
            string s;
            cin >> s;
            cout << susunan_kata(s) << "\n";
        } else {
            long long b, k;
            cin >> b >> k;
            cout << kombinasi((int)(b - 1 + k - 1), (int)(b - 1)) << "\n";
        }
    }

    jalankan_penguji();
    return 0;
}