Arko is very fond of permutations. He can easily calculate the number of length permutations. (In which permutations there contained numbers from 1 to are called length permutations. is called a 4 length permutations.). So his teacher give him a tricky problem on permutations. He has to calculate the number of length permutations where specific values will be in same order.
There are total 6 permutations of 3 length. If two specific number in the same order the valid permutations will be:
*
*
*
So there are totally 3 valid permutations when in the same order in 3 length permutations.
Arko didn’t able to solve this problem. Can you help him?
The first line will contain two numbers and (, ).
Next line will contain distinct numbers ().
You have to print the number of valid permutations. The answer can be very large. So you have to print the answer mod .
Input | Output |
---|---|
3 2 3 2 | 3 |