123456789 찾기

문자열 S와 P가 주어진다. S 안에서 P가 나타나는 시작 위치 가운데 하나 이상을 골라, 고른 위치를 모두 곱한 값이 1부터 9까지의 모든 자연수로 나누어떨어지도록 하는 방법의 수를 구하시오.

시작 위치는 S의 첫 글자를 1번으로 하여 센다. P가 나타나는 구간은 서로 겹쳐도 된다. 고른 시작 위치의 집합이 다르면 서로 다른 방법으로 센다.

예를 들어 P = "a", S = "aaaaaaa"라면 조건을 만족하는 방법은 {1, 2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}, {3, 4, 5, 6, 7}, {1, 3, 4, 5, 6, 7}의 네 가지다.

첫째 줄에 P가, 둘째 줄에 S가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 1 이상 10,000 이하이다.

첫째 줄에 조건을 만족하는 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.