D-CaesarQueries

#include <bits/stdc++.h>
#pragma warning (disable : 26451)
#pragma warning (disable : 4996)
#define mod 666013
using namespace std;
ifstream fin("caesar.in");
ofstream fout("caesar.out");
int main() {
	int lg = 2000;
	vector<int> fact(lg + 1);
	fact[0] = 1;
	for (int i = 1; i <= lg; ++i) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= mod;
	}
	vector<vector<int>> dp(lg + 1, vector<int>(lg + 1));
	dp[1][1] = 1;
	for (int i = 2; i <= lg; ++i) {
		for (int j = 1; j <= lg; ++j) {
			dp[i][j] = ((dp[i - 1][j] * j) % mod + dp[i - 1][j - 1]) % mod;
		}
	}
	int q;
	fin >> q;
	for (int i = 1; i <= q; ++i) {
		int n, k;
		fin >> n >> k;
		fout << (1ll * dp[n][k] * fact[k]) % mod << '\n';
	}
	cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}