24970번 - 균형 수

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

12321는 처음 ⌈5/2⌉ 자리의 합이 1 + 2 + 3 = 6, 마지막 ⌈5/2⌉ 자리의 합이 3 + 2 + 1 = 6으로 서로 같기 때문에, 균형 수이다. 13722도 1 + 3 + 7 = 7 + 2 + 2 이기 때문에 균형 수이다.

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

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

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

• 1 ≤ N ≤ 100