391 . Narayana number
Description
In combinatorics, the Narayana numbers N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, form a triangle of natural numbers, called Narayana triangle, that occur in various counting problems. They are named for T.V. Narayana, a mathematician from India.
The Narayana numbers can be expressed in terms of binomial coefficients:
In the problem, you need to compute N(n, k) modulo 32771.
Input Format
The first line of the input contains a single integer T (1 <= T <= 200), the number of test cases. Then T cases follow. Every case is a line containing two integers n and k (1<=k<=n<=109).
Output Format
For each test case, output a integer N(n, k) mod 32771.
Sample Input 1
2 1 1 6 3
Sample Output 1
1 50
Hints
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|