Input
2 3
3
Output
1
Input
0 -1
2
Output
1000000006