## Let’s take a step to Unlock the Dark Web Door

Our Friend Monk has finally found the **Door of Dark Web secrets**. However, the door of the Dark Web is firmly locked. Now, as per the rules of the Dark Web, Monk needs to enter a **Secret Password** in a special language to unlock the door. This language, unlike English, consists of alphabets. The properties of this secret password are:

- It has a length of characters.
- It is composed only of the K characters belonging to the Special language.
- Each character belonging to the special language has been used
**at max once**in the secret code.

Now, Monk has no idea about what the ideal password may be and needs your help. You need to help Monk find the total number of **distinct** candidate Strings for it **Modulo**

## Input Format

The first line contains a single integer denoting the number of test cases. Each of the next T lines contains two integers N and K denoting the length of the Secret Password and the number of characters of the Special language to be used respectively.

**Output Format**:

For each test case, output the number of possible distinct secret passwords **Modulo**

## Constraints

## Note:

You need to print the value of each element and not their weight.

## SAMPLE INPUT

1 3 3

## SAMPLE OUTPUT

6

## Explanation

Let’s number the characters of the special language to be , and respectively. So, all possible candidate Strings are:

So, here we have 6 possible passwords. So, the answer =

As is always less than or equal to , an answer greater than shall always exist. Any character among the available characters can be used at most once in a single password. So, we need to select characters out of the K available characters for a single password. So, the total number of ways to select N characters among K characters is K Choose N. ( K C N ). Any selected group of characters can then be permuted among themselves in ways. So, the answer to the problem is :

%

We can pre-compute all factorials and get the inverse factorials by using Fermat’s Little Theorem as is a prime number. Each query can then be answered in

So, overall time complexity is : , where max n =

Pingback: 24 GB Free Data on Vodafone || Let's Grab it - Code@ter Blog