#include #include using namespace std; const int PERIOD[8] = {0, 0, 0, 6, 6, 12, 60, 60}; const int MOD = 1000000000 + 7; const int MAX_BRUTE_N = 1000; const int MAX_FACTORIAL = 1000000; const int MAX_BRUTE_K = 7; int answer[MAX_BRUTE_N + 10][MAX_BRUTE_K + 10]; int dp[2][MAX_BRUTE_N * (MAX_BRUTE_K + 1) + 10][MAX_BRUTE_K + 2], c[MAX_BRUTE_K + 10][MAX_BRUTE_K + 10], tn, n, k; int inverse[MAX_BRUTE_N], ps[MAX_BRUTE_K + 10]; int fact[MAX_FACTORIAL + 10]; int get_factorial (int n) { if (n <= MAX_FACTORIAL) return fact[n]; int ret = 1; for(int i = 1; i <= n; i++) ret = (ret * 1LL * i) % MOD; return ret; } inline int divide (int a, int b) { return a * 1LL * inverse[b] % MOD; } int solve (int n, int k) { int e = 0, ret = 0; int start = n % PERIOD[k]; int finish = start + k * PERIOD[k]; for(int i = start; i <= finish; i += PERIOD[k]) { ps[e] = i; c[0][e++] = answer[i][k]; } for(int i = 1; i < e; i++) for(int j = 0; j < e - i; j++) c[i][j] = divide((c[i - 1][j + 1] - c[i - 1][j] + MOD) % MOD, (i) * PERIOD[k]); int current_prod = 1; for(int i = 0; i < e; i++) { if (i >= 1) current_prod = (current_prod * 1LL * (n - ps[i - 1] + MOD)) % MOD; ret = (ret + current_prod * 1LL * c[i][0]) % MOD; } return ret; } inline void update (int &a, int b) { a += b; if (a >= MOD) a -= MOD; } int binpow (int x, int y) { int ret = 1, carry = x; for(int i = 0; (1 << i) <= y; i++) { if (y & (1 << i)) ret = (ret * 1LL * carry) % MOD; carry = (carry * 1LL * carry) % MOD; } return ret; } void precalc_inverses () { inverse[0] = 1; for(int i = 1; i <= MAX_BRUTE_N; i++) inverse[i] = binpow(i, MOD - 2); fact[0] = 1; for(int i = 1; i <= MAX_FACTORIAL; i++) fact[i] = fact[i - 1] * 1LL * i % MOD; } void precalc_brute_table () { dp[0][0][0] = 1; for(int i = 1; i <= MAX_BRUTE_N; i++) { for(int j = 1; j <= MAX_BRUTE_K; j++) update(answer[i][j], answer[i - 1][j]); int l = i % 2; int p = 1 - l; for(int j = 0; j <= i * MAX_BRUTE_K; j++) for(int k = 0; k <= MAX_BRUTE_K; k++) dp[l][j][k] = 0; for(int j = 0; j <= (i - 1) * MAX_BRUTE_K; j++) for(int k = 0; k <= MAX_BRUTE_K; k++) if (dp[p][j][k]) { update(dp[l][j][k], dp[p][j][k]); update(dp[l][j + i][k + 1], dp[p][j][k]); if (i < j) update(answer[i][k + 1], dp[p][j][k]); } } } int main(int argc, const char * argv[]) { precalc_inverses(); precalc_brute_table(); cin >> tn; while (tn--) { cin >> n >> k; int p1 = solve(n, k); cout << p1 % MOD << endl; } return 0; }