Modulo Solitaire

Modulo Solitaire is a game you can play when you are bored, even on paper without a phone. First you pick a modulus $m$. Then you pick $n$ pairs of numbers $(a_i, b_i)$. Finally you pick a starting number $s_0$. Your goal is to reach $0$ from $s_0$ in as few moves as possible.

In each move you choose an index $i$ (with $1 \le i \le n$), then replace your current number $s$ by $(s \cdot a_i + b_i) \bmod m$. In other words, if $s_{j-1}$ is your number just before the $j$-th move and you choose index $i$, then $s_j = (s_{j-1} \cdot a_i + b_i) \bmod m$.

Determine the smallest number of moves needed to turn $s_0$ into $0$.

The first line contains three integers $m$, $n$, and $s_0$ with $0 < m \le 10^6$, $0 \le n \le 10$, and $0 < s_0 < m$.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ with $0 \le a_i \le 10^9$ and $0 \le b_i \le 10^9$.

Output a single integer: the smallest number of moves needed to reach $0$ starting from $s_0$. If $0$ can never be reached, output $-1$.