Finding 123456789

Time limit1sMemory limit512 MB

Summary

Count subsets of occurrences of P in S whose starting positions multiply to a common multiple of 1 through 9, modulo 1000000007.

Level: Medium6 of 10
Topics: Dynamic programming, String matching, Number theory
Solved: No attempts yet

Problem

You are given two strings S and P. Choose one or more of the starting positions where P occurs in S so that the product of the chosen positions is divisible by every natural number from 1 to 9. Count how many such choices exist.

Starting positions are counted with the first character of S as position 1. Occurrences of P may overlap. Two choices are different when the sets of chosen starting positions differ.

For example, if P = "a" and S = "aaaaaaa", the choices that satisfy the condition are {1, 2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}, {3, 4, 5, 6, 7} and {1, 3, 4, 5, 6, 7}, so there are four of them.

Input

The first line contains P and the second line contains S. Both strings consist of lowercase letters only, and each length is between 1 and 10,000.

Output

Print the number of choices that satisfy the condition, modulo $10^9+7$ .

Examples3

Example 1
Input
```
a
aaaaaaa
```
Expected output
```
4
```
Example 2
Input
```
aa
aaaaaaaaaaaaaaaaa
```
Expected output
```
35544
```
Example 3
Input
```
aa
aaaaaaaacaaaadaaafajaiaaaaaa
```
Expected output
```
53712
```