This problem is a programming version of Problem 168 from projecteuler.net
Consider the number . We can right-rotate this number by moving the last digit to the front of it, giving us .
It can be verified that .
This demonstrates an unusual property of 142857: it is a divisor of its right-rotation.
Find the last 5 digits of the sum of all integers , , that have this property.
Input Format
One integer is given on first line representing .
Constraints
Output Format
Print one integer which is the answer to the problem.
Sample Input 0
2
Sample Output 0
495