Input
3 2 8
Output
3
10 2008 13726
Input
1 2 -18
Output
0
Input
2 2 -1
Output
4
1 31 337 967