Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito tiene ha generado un número muy grande de forma aleatoria. La distribución de probabilidades usada fue la uniforme por lo que todos los dígitos tienen igual probabilidad de ocurrir. Fito supone que por esta razón todo número de dos dígitos debe también tener la misma probabilidad de aparecer como substring de su número. Siguiendo esta línea de pensamiento Fito quiere comprobar cuántos números de $D$ dígitos aparecen como substring del número generado. Para evitar buscar todos los números Fito restringe el rango a los números entre $A$ y $B$ incluidos. Los números $A$ y $B$ tienen $D$ dígitos.

Después de hacer varias pruebas, Fito encuentra que a pesar de ser tan grande su número no contiene a todos los del intervalo. Para aumentar la cantidad de números que aparecen como substring, decide entonces cambiar la definición de ocurrencia. Ahora considera que un número aparece en el texto, si ambos tienen un substring común de al menos la mitad de la longitud del número. En nuestro caso la longitud del substring común debe ser $\lfloor{\frac{D}{2}}\rfloor$.

La primera línea de la entrada contiene un entero $T (1 \leq T \lt 10^{1000})$ el número generado por Fito. La segunda y tercera líneas tienen los enteros $A$ y $B (10 \leq A \leq B \lt 10^{50})$ respectivamente. Los enteros $A$ y $B$ no tienen ceros a la izquierda y tienen la misma cantidad de dígitos.

Se debe imprimir la cantidad de número entre $A$ y $B$ que aparecen en el número generado por Fito usando su nueva definición de ocurrencia. Como el resultado puede ser muy grande, imprímalo módulo $1000000007$.