Luka is bored in chemistry class so he is staring at a large periodic table of chemical elements hanging from a wall above the blackboard. To kill time, Luka decided to make his own table completely different from the one in the classroom.
His table consists of
After he draws the table he needs to fill it with elements. He first decided to enter the noble gases of which there are
Two squares in the table are close to each other if they are in the same column or row, and all squares between them exist. In the example below, the a
squares are not close, but the b
squares are.
b | ||||
a | a | |||
b |
Write a program that, given
Input Specification
The first line contains the integers
The next line contains
Output Specification
Output the number of ways for Luka to fill his table with noble gases, modulo
Scoring
In test cases worth
Sample Input 1
3 3
2 1 3
Sample Output 1
2
Sample Input 2
4 1
1 2 3 4
Sample Output 2
10
Sample Input 3
5 2
2 3 1 2 4
Sample Output 3
43
Sample Input 4
3 2
999999 999999 999999
Sample Output 4
990979013
Comments