Problem Description

A number is a drr1 number if it is a divisor of its right rotation by one digit.
For example, consider the number 102564, its one-digit-right-rotation is 410256, and we have 410256 = 4 * 102564, so it is a drr1 number.
Give you an integer n, what is the sum of all drr1 numbers between 10 and 10^n?

Input

An integer n, 1 <= n <= 1000

Output

The result mod 100000

2
100

495
59206