Let us define be number of subsets of K distinct elements of S where N is the size of S. Given a , let .
You have to print Sum modulo .
Input:
First line contains, T, the number of testcases. Each testcase consists of N and P in one line.
Output:
Print required answer in one line for each testcase.
**Constraints:
Here is the explanation of the test case: S contains distinct elements
First Test Case:
so value of Sum will be equal to
As S contains distinct elements let
Subsets of S are:
{}--> length 0
{1} --> length 1
{2} --> length 1
{} --> length 2
So value of because there is only one null subset {}
value of because there is two subset which contain distinct elements .
value of because there is only one subset which contains two distinct values
