Rhezo calls a number good if the number is divisible by all numbers from 1 to 9. His father also likes good numbers, and has promised him to buy 1 chocolate per every good number he tells him. He doesn't want to make the task simple for Rhezo, therefore he gives him 2 strings T and P.

He tells Rhezo to find the number of ways to select one or more occurrences of P in T, so that the product of starting positions of all those occurrences is a good number. Rhezo likes chocolates and is not so good at programming. Help him. As the answer could be large, output the answer modulo $10^9+7$.

Input:

First line contains the string P. Second line contains the string T.

Output:

Help Rhezo to find the number of ways to select one or more occurrences of P in T, so that the product of starting positions of all those occurrences is a good number.

Constraints:

Length of $S, T \le 10^4$