Натуральное число, имеющее k десятичных цифр, называется уравновешенным, если сумма его первых ⌈^k/₂⌉ цифр равна сумме его последних ⌈^k/₂⌉ цифр, где ⌈x⌉, читается округление вверх x - наименьшее целое число ≥ x, таким образом ⌈π⌉ = 4 и ⌈5⌉ = 5.

Так, к примеру, все палиндромы уравновешены, равно как и число 13722.

Пусть T(n) будет суммой всех уравновешенных чисел меньше 10ⁿ.
Таким образом, T(1) = 45, T(2) = 540 и T(5) = 334795890.

Найдите T(47) mod 3¹⁵.