Here we will learn about two very common concepts in Probability and Statistics -
Combinations and
Permutations. Generally, these involve selecting
k objects from a set of n options.
Before we dive in, there is one more concept we must explore -
Factorials. These are typically written with an
exclamation point like 5!, or as factorial(5). To compute, we multiply that integer by every
positive integer smaller than itself, so 5! = 5 * 4 * 3 * 2 * 1 = 120.
Let's imagine we have a bag of 26 wooden letters, A through Z. You take three turns, each
time removing a letter from the bag, writing it down, then placing it back into the bag. After
doing this a few time we end up with words like KFF, BQH, and KFK. This method is called
Permutations with Replacement. The total quantity of possible words is n ^ k, because for
each choice we may use any of the possible options. In this example, 26 ^ 3 = 17576.
Now let's do the same thing, but we'll consider words that contain the same elements in different
order to be the same. For example KFF and KFK would no longer be considered two unique words.
This method would be called Combinations with Replacement. The total quantity of possible words
is (n + k - 1)! / ((n - 1)! * k!). In this example, 28! / (25! * 3!) = 3276.
Now let's go back to Permutations, but this time we will not replace the letters back into the bag
after removing them, so now words like KFF are no longer possible, but BQH and QHB would
still be considered unique. This is called Permutations without Replacement. The total
quantity of possible words is n! / (n - k)!. In this example, 26! / 23! = 15600.
If we do not replace the letters and don't consider words of different orders to be unique,
this is Combinations without Replacement. The total quantity of possible words is
n! / ((n - k)! * k!). In this example, 26! / (23! * 3!) = 2600.
Input Data
The first line will contain Q, the quantity of testcases.
Q lines will follow, each containing three values - n, k, and then one of four possible
values indicating which of the above situations is being modeled:
PR for Permutations with ReplacementCR for Combinations with ReplacementP for Permutations without ReplacementC for Combinations without ReplacementAnswer
Should be a string of Q space-separated values, corresponding to the number of subgroups
possible for each testcase.
As values may get quite large, report all answers modulo 1000000007.
Example
input data:
11 4 PR
21 9 CR
41 11 P
501 123 C
answer:
14641 10015005 601453130 29823016