cho.sh

Finding 123456789

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

Medium6Dynamic programmingString matchingNumber theoryNo attempts yetTime limit1sMemory limit512 MB

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 109+710^9+7.