시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

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

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

f^1(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

출처