Luka found an interesting tape in the chem lab. The tape is divided into
One side of the tape is completely covered with a very volatile chemical. If the chemical
comes in contact with itself, it reaches critical mass and explodes.
The other side of the tape is not completely covered yet. Only the first
Write a program that will calculate the number of different ways Luka can bend the tape so that it does not explode. He can bend the tape more than once and two ways are different if there is at least one bevel between segments that is not bent in one and is bent in the other.
Since the solution can be huge, print the result modulo
The following example illustrates all
Input Specification
The first and only line of input contains three natural numbers
Output Specification
The first and only line of output should contain the number of possible ways to bend
the tape modulo
Sample Input 1
4 1 1
Sample Output 1
6
Sample Input 2
5 2 2
Sample Output 2
1
Sample Input 3
6 1 2
Sample Output 3
7
Comments