12105번 - 123456789 찾기

문제

문자열 S와 P가 주어졌을 때, S에서 P를 하나 또는 그 이상 찾는 방법의 수를 구하는 프로그램을 작성하시오. 이때, S에서 찾은 P의 시작 위치를 모두 곱한 수가 1부터 9까지의 자연수로 모두 나누어 떨어져야 한다.

예를 들어, 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가 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 문제의 조건대로 찾는 방법의 수를 10⁹+7로 나눈 나머지를 출력한다.

제한

힌트