모듈로 솔리테어

모듈로 솔리테어는 심심할 때 즐길 수 있는 게임으로, 휴대폰 없이 종이만 있어도 할 수 있다. 먼저 법(modulus) $m$을 정한다. 그다음 $n$개의 수 쌍 $(a_i, b_i)$를 정한다. 마지막으로 시작 수 $s_0$을 정한다. 목표는 $s_0$에서 시작하여 가능한 한 적은 횟수의 이동으로 $0$에 도달하는 것이다.

각 이동에서는 인덱스 $i$($1 \le i \le n$)를 하나 고른 뒤, 현재 수 $s$를 $(s \cdot a_i + b_i) \bmod m$으로 바꾼다. 즉, $j$번째 이동 직전의 수가 $s_{j-1}$이고 인덱스 $i$를 골랐다면 $s_j = (s_{j-1} \cdot a_i + b_i) \bmod m$이 된다.

$s_0$을 $0$으로 만드는 데 필요한 최소 이동 횟수를 구하여라.

첫째 줄에 세 정수 $m$, $n$, $s_0$이 주어진다. ($0 < m \le 10^6$, $0 \le n \le 10$, $0 < s_0 < m$)

이어지는 $n$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어진다. ($0 \le a_i \le 10^9$, $0 \le b_i \le 10^9$)

$s_0$에서 시작하여 $0$에 도달하는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다. 어떤 방법으로도 $0$에 도달할 수 없다면 $-1$을 출력한다.