Modulo Solitaire is a game that can be played when you are bored. You can even play it without a phone, just on paper. First, you pick a number m. Then you pick two sequences of numbers a_i and b_i. Finally, you pick a starting number s₀. Now, your goal is to go from s₀ to 0 in as few moves as possible. In each move, you choose an i, then multiply your current number by a_i, add b_i to it, and reduce the result modulo m. That is, s_j = (s_j-1 * a_ij + b_ij) % m.

The first line of input contains three integers 0 < m <= 1000000, 0 <= n <= 10, and 0 < s₀ < m. The next n lines each contain two integers, a pair 0 <= a_i <= 1000000000 and 0 <= b_i <= 1000000000.

Output a single integer, the shortest number of moves needed to reach 0 starting from s0. If it is not possible to reach 0 in any number of moves, output -1.

Waterloo180210