균형 수

시간 제한1초메모리 제한1024 MB

요약

N이 주어지면 10^N 이하의 균형 수를 모두 더한 값을 315로 나눈 나머지로 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

처음 $\lceil K/2 \rceil$ 자리의 합과 마지막 $\lceil K/2 \rceil$ 자리의 합이 같은 길이가 K인 양의 정수를 균형 수라고 한다. $\lceil x \rceil$ 는 x보다 크거나 같은 가장 작은 정수를 의미한다. 예를 들어, $\lceil \pi \rceil = 4$ , $\lceil 5 \rceil = 5$ 이다.

12321은 처음 $\lceil 5/2 \rceil$ 자리의 합이 1 + 2 + 3 = 6, 마지막 $\lceil 5/2 \rceil$ 자리의 합이 3 + 2 + 1 = 6으로 같기 때문에 균형 수이다. 13722도 1 + 3 + 7 = 7 + 2 + 2이므로 균형 수이다.

$T(n)$ 은 $10^n$ 보다 작거나 같은 모든 균형 수의 합이다. $T(1) = 45$ , $T(2) = 540$ , $T(5) = 334795890$ 이다. N이 주어졌을 때, $T(N)$ 을 출력하라.

입력

첫째 줄에 양의 정수 N이 주어진다.

출력

첫째 줄에 $T(N)$ 을 315로 나눈 나머지를 출력한다.

제한

$1 \le N \le 100$

예제4

예제 1
입력
```
1
```
예상 출력
```
45
```
예제 2
입력
```
2
```
예상 출력
```
540
```
예제 3
입력
```
5
```
예상 출력
```
4771029
```
예제 4
입력
```
100
```
예상 출력
```
10453080
```