10-подстрока числа - это подстрока его цифр, дающих в сумме 10. Например, 10-подстроками числа 3523014 являются:

• 3523014
• 3523014
• 3523014
• 3523014

Число называется дружественным к 10-подстрокам, если каждая его цифра принадлежит 10-подстроке. Например, 3523014 дружественно к 10-подстрокам, а 28546 - нет.

Пусть T(n) будет количеством дружественных к 10-подстрокам чисел от 1 до 10ⁿ (включительно).
Например, T(2) = 9 и T(5) = 3492.

Найдите T(10¹⁸) mod 1 000 000 007.