십진법으로 k자리인 자연수 중에서 앞 ⌈^k/₂⌉ 자릿수의 합이 뒤 ⌈^k/₂⌉ 자릿수의 합과 같으면 균형 잡혔다고 합니다. 여기서 ⌈x⌉는 , x의 천장(ceiling) 함수값으로 x보다 크거나 같은 최소 정수로 정의 됩니다. 즉, ⌈π⌉ = 4이고 ⌈5⌉ = 5입니다.

예를 들어, 모든 대칭수(palindrome)는 균형 잡힌 수이고, 13722같은 수도 균형 잡힌 수입니다.

T(n)을 10ⁿ미만인 모든 균형 잡힌 수의 총합이라고 합시다.
그러면: T(1) = 45, T(2) = 540이고 T(5) = 334795890입니다.

T(47) mod 3¹⁵ 값을 구하세요.