f(X) = A + X + B + X + C로 정의되어 있는 함수가 있다. 여기서 X는 문자열이고, +는 문자열 연결을 나타내는 연산이다. A, B, C는 비어있지 않은 상수 문자열이다.</p>

다섯 문자열 A, B, C, S, F와 정수 K가 주어진다.

이때, f^K(S)에 F가 부분 문자열로 총 몇 번 등장하는지 구하는 프로그램을 작성하시오.

f¹(X) = f(X)이고, f^K(X) = f(f^K-1(X))와 같다.

입력 형식

첫째 줄에 A, B, C, S, F, K가 주어진다. A, B, C, S, F는 길이가 50보다 작거나 같은 알파벳 소문자로 이루어진 문자열이고, K는 10,000,000보다 작거나 같은 자연수이다.

출력 형식

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

예제 입력 1

a b c x axb 2

예제 출력 1

2

예제 입력 2

a b c x abcdefghij 1

예제 출력 2

0

예제 입력 3

a b c d baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba 58

예제 출력 3

191690599

예제 입력 4

a x y b aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab 49

예제 출력 4

1