Balanced numbers

Time limit1sMemory limit1024 MB

Summary

Given N, sum every balanced number up to 10^N, where the first and last ceil(K/2) digits have equal digit sums, and print the total modulo 315.

Level: Medium6 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

A positive integer of length K is called balanced if the sum of its first $\lceil K/2 \rceil$ digits equals the sum of its last $\lceil K/2 \rceil$ digits. $\lceil x \rceil$ is the smallest integer greater than or equal to x. For example, $\lceil \pi \rceil = 4$ and $\lceil 5 \rceil = 5$ .

12321 is balanced because the first $\lceil 5/2 \rceil$ digits sum to 1 + 2 + 3 = 6, and the last $\lceil 5/2 \rceil$ digits sum to 3 + 2 + 1 = 6. 13722 is also balanced because 1 + 3 + 7 = 7 + 2 + 2.

$T(n)$ is the sum of all balanced numbers less than or equal to $10^n$ . $T(1) = 45$ , $T(2) = 540$ , and $T(5) = 334795890$ . Given N, print $T(N)$ .

Input

The first line contains a positive integer N.

Output

On the first line, print $T(N)$ modulo 315.

Constraints

$1 \le N \le 100$

Examples4

Example 1
Input
```
1
```
Expected output
```
45
```
Example 2
Input
```
2
```
Expected output
```
540
```
Example 3
Input
```
5
```
Expected output
```
4771029
```
Example 4
Input
```
100
```
Expected output
```
10453080
```