rhezo-and-division

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 ≤ 10^4

SAMPLE INPUT
a
aaaaaaa

SAMPLE OUTPUT
4

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

String algorithms


Solutions: