Problem 529
10-substrings
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:
- 3523014
- 3523014
- 3523014
- 3523014
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 10n (inclusive).
For example T(2) = 9 and T(5) = 3492.
Find T(1018) mod 1 000 000 007.
10-子串
一个数的10-子串指的是其各位数字和为10的子串。例如，数3523014的10-子串包括：
- 3523014
- 3523014
- 3523014
- 3523014
如果一个数的每一位数字都包含在一个10-子串当中，那么这个数被称为10-子串友好数。例如，3523014是10-子串友好数，而28546则不是。
记T(n)是1至10n之间（包含1和10n）所有10-子串友好数的数目。
已知T(2) = 9以及T(5) = 3492。
求T(1018) mod 1 000 000 007。