f(X) = A + X + B + X + C

문자열 $X$를 받아 $f(X) = A + X + B + X + C$를 돌려주는 함수 $f$가 있다. 여기서 $+$는 문자열 연결 연산이고, $A$, $B$, $C$는 비어 있지 않은 상수 문자열이다.

함수를 여러 번 적용한 결과는 $f^1(X) = f(X)$, $f^K(X) = f(f^{K-1}(X))$로 정의한다.

문자열 $A$, $B$, $C$, $S$, $F$와 정수 $K$가 주어진다. $f^K(S)$에 $F$가 부분 문자열로 몇 번 등장하는지 구하는 프로그램을 작성하시오. 시작 위치가 다르면 서로 겹치더라도 각각 센다.

첫째 줄에 $A$, $B$, $C$, $S$, $F$, $K$가 공백으로 구분되어 주어진다. $A$, $B$, $C$, $S$, $F$는 길이가 1 이상 50 이하이고 알파벳 소문자로만 이루어진 문자열이다. $K$는 10,000,000보다 작거나 같은 자연수이다.

첫째 줄에 $f^K(S)$에 $F$가 부분 문자열로 등장하는 횟수를 1,000,000,007로 나눈 나머지를 출력한다.