Unlock the Dark Web Door || Medium Problem

      1 Comment on Unlock the Dark Web Door || Medium Problem

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:

  1. It has a length of  characters.
  2. It is composed only of the K characters belonging to the Special language.
  3. 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 = 

{Code With Code@ter}

Give Your Reviews

1 comment on “Unlock the Dark Web Door || Medium Problem

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

Leave a Reply