Periodni
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 N columns, each with some height, aligned at the bottom (see example below). After he draws the table he needs to fill it with elements. He first decided to enter the noble gases of which there areK. Luka must put them in the table so that no two noble gases are close to each other.
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.
Write a program that, given N, K and the heights of the N columns, calculates the total number of ways for Luka to place the noble gases into the table. This number can be large, so output it modulo 1 000 000 007.
Input
3 3
2 1 3
Output
2 Input
4 1
1 2 3 4
Output
10 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.