### Problem Statement

Given are two Strings P1 and P2. Each of these strings contains a pattern of zeros and ones.

The string S(n) is formed by concatenating 1,000,000 copies of P1 followed by n copies of P2.

The infinite string S is formed by concatenating the strings S(1), S(2), S(3), ... in this order.

The string T consists of the first 10^16 characters of the string S.

We are interested in substrings of T that are zeroCount characters long and contain only zeros. Write a method that finds the first occurrence of such a substring in T, and returns the zero-based index of its first character. In case T contains no such substring return -1.

### Definition

 Class: RepeatedPatterns Method: findZeroSegment Parameters: String, String, String Returns: long Method signature: long findZeroSegment(String P1, String P2, String zeroCount) (be sure your method is public)

### Notes

-The number zeroCount may be large, and therefore it is specified as a String.

### Constraints

-P1 will contain between 1 and 50 characters, inclusive.
-P2 will contain between 1 and 50 characters, inclusive.
-P1 and P2 will contain only zeroes ('0') and ones ('1').
-zeroCount will contain between 1 and 17 characters, inclusive.
-zeroCount will contain only digits ('0'-'9').
-zeroCount will represent a positive integer between 1 and 10^16, inclusive.
-zeroCount will not contain leading zeros.

### Examples

0)

 `"111010100001010"` `"010000001000"` `"3"`
`Returns: 7`
 The first occurrence of three consecutive zeroes is right in the first copy of P1.
1)

 `"1101010010"` `"0001000"` `"3"`
`Returns: 9999999`
 This time the first substring "000" starts with the last character of the 1,000,000th copy of P1.
2)

 `"1101010010"` `"0001000"` `"5"`
`Returns: 20000011`
 We have the same string T as in Example 1, only we look for the substring "00000". The first occurrence is between the second and the third copy of P2.
3)

 `"10101010"` `"101010101010"` `"9876543219876"`
`Returns: -1`
 Nowhere in the infinite string S can we find two consecutive zeroes. Clearly, in the string T there is no substring with 9876543219876 consecutive zeroes.
4)

 `"11111111111111111111111111"` `"0"` `"9876543219876"`
`Returns: -1`
 The infinite string S does contain 9876543219876 consecutive zeroes. However, the first occurrence is too far, thus the string T doesn't contain it.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7294

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10657&pm=7294

misof

#### Testers:

PabloGilberto , brett1479 , Olexiy , Mike Mirzayanov

Greedy