5607.cpp

// 5607. 조합
// 2019.07.05
#include <iostream>

using namespace std;

const long long p = 1234567891;
// 거듭제곱 재귀
long long pow(long long x, long long y)
{
	long long r = 1;
	while (y > 0)
	{
		if (y % 2)
		{
			r *= x;
			r %= p;
		}
		x *= x;
		x %= p;
		y /= 2;
	}
	return r;
}

int main()
{
	long long n, k;
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cin >> n >> k;
		long long A = 1;
		long long B = 1;
		// n!
		for (long long i = n; i >= 1; i--)
		{
			A *= i;
			A %= p;
		}
		// k!
		for (long long i = k; i >= 1; i--)
		{
			B *= i;
			B %= p;
		}
		// k! * (n-k)!
		for (long long i = n - k; i >= 1; i--)
		{
			B *= i;
			B %= p;
		}
		cout << "#" << i << " " << (A*pow(B, p - 2)) % p << endl;
	}
	return 0;
}