0의 연속 패턴

0과 1로만 이루어진 두 문자열 S1과 S2가 주어진다. 양의 정수 N에 대해 S(N)은 S1을 1,000,000번 이어 붙인 뒤, S2를 N번 이어 붙인 문자열이다.

무한 문자열 S는 S(1), S(2), S(3), ...을 차례대로 이어 붙여 만든다. T는 S의 처음 10^16개 문자로 이루어진 문자열이다.

T의 부분 문자열 중 길이가 C이고 모든 문자가 0인 것이 처음 나타나는 위치를 구하라. 위치는 0부터 시작한다.

첫째 줄에 S1, 둘째 줄에 S2가 주어진다. 두 문자열은 0과 1로만 이루어져 있으며, 각각의 길이는 50 이하이다.

셋째 줄에는 자연수 C가 주어진다. C <= 10^16이다.

정답을 한 줄에 출력한다. 조건을 만족하는 부분 문자열이 없다면 -1을 출력한다.