Zero Run Pattern

Two binary strings S1 and S2 are given. For a positive integer N, define S(N) as the string made by concatenating 1,000,000 copies of S1, followed by N copies of S2.

The infinite string S is formed by concatenating S(1), S(2), S(3), ... in order. Let T be the first 10^16 characters of S.

Find the first position in T where a substring of length C consisting only of 0 appears. Positions are 0-based.

The first line contains S1, and the second line contains S2. Each string consists only of 0 and 1, and each has length at most 50.

The third line contains the positive integer C, where C <= 10^16.

Print the answer on one line. If no such substring exists, print -1.