시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 74 7 6 22.222%

문제

두 문자열 S1과 S2가 있다. 이 문자열은 0과 1의 패턴으로 이루어져 있다.

문자열 S(N)은 S1을 1,000,000개 연결한 다음에 S2를 N개 연결한 것이다.

길이가 무한인 문자열 S는 S(1), S(2), S(3), …을 순서대로 계속 연결한 것이다.

문자열 T는 문자열 S의 처음 10^16개 문자이다.

자 이제, T의 부분 문자열 중에 길이가 C이면서 0으로만 이루어진 것을 찾으려고 한다. 이러한 부분 문자열의 T에서 가장 처음 나타나는 위치를 구하는 프로그램을 작성하시오. 문자열의 위치는 0부터 시작한다.
 

입력

첫째 줄에 S1이 주어지고, 둘째 줄에 S2가 주어진다. S1과 S2는 0과 1로만 이루어져 있고, 길이는 최대 50이다. 셋째 줄에는 C가 주어진다. C는 10^16보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 그러한 부분 문자열이 없다면 -1을 출력한다.

예제 입력

111010100001010
010000001000
3

예제 출력

7

힌트

출처