Super symmetric

We define a string of digits is symmetric as if we obtain the same results when reading it from right to left or vice versa. Example: 3, 121, 78987, ... are symetric.

A string S has k digits is called supersymmetric if following conditions are satisfied:

• S[1..k] is symmetric;
• S[1..k div 2] is symmetric;
• S[k — k div 2 + 1..k] is symmetric.

For example: 0, 11, 22322,... are supersymmetric numbers.

A number is almost-supersymmetric (the first digit is always different from 0) is defined as if we could change the position of some of its digits to make a supersymmetric number (note: after changing, the first digit may be zero). For example: 8404000 is almost-supersymmetric, since 0408040 is supersymmetric.

Find out how many almost-supersymmetric numbers between l and r (1 <= l <= r <= 1e50000). Print the remainder for 1e9+7.

Example 1: Input l = 3111120 r = 3111125 Output: 2

Note: 2 almost-supersymmetric numbers are 3111122 and 3111123.

Example 2: Input l = 1 r = 100 Output: 19

Note: almost-supersymmetric numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 100.