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 ofalphabets. The properties of this secret password are:
- It has a length of characters.
- It is composed only of the 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
The first line contains a single integerdenoting the number of test cases. Each of the next lines contains two integers and denoting the length of the Secret Password and the number of characters of the Special language to be used respectively.
For each test case, output the number of possible distinct secret passwords Modulo
You need to print the value of each element and not their weight.
1 3 3
Let’s number the characters of the special language to be, and respectively. So, all possible candidate Strings are:
So, here we havepossible passwords. So, the answer =
Asis 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 available characters for a single password. So, the total number of ways to select characters among characters is K Choose 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 asis a prime number. Each query can then be answered in
So, overall time complexity is :, where max n =