## 10-substrings

### Problem 529

A *10-substring* of a number is a substring of its digits that sum to 10. For example, the 10-substrings of the number 3523014 are:

3014__352__- 3
014__523__ - 3
14__5230__ - 35
__23014__

A number is called *10-substring-friendly* if every one of its digits belongs to a 10-substring. For example, 3523014 is 10-substring-friendly, but 28546 is not.

Let `T`(`n`) be the number of 10-substring-friendly numbers from 1 to 10^{n} (inclusive).

For example `T`(2) = 9 and `T`(5) = 3492.

Find `T`(10^{18}) mod 1 000 000 007.