C++ :

#include<bits/stdc++.h>
#define maxn 1001000
using namespace std;
int dis[maxn];
int m,n,s0,a[20],b[20],q[maxn],l,r;
int main(){
	scanf("%d%d%d",&m,&n,&s0);
	q[r++]=s0,dis[s0]=1;
	for(int i=1;i<=n;++i)scanf("%d%d",&a[i],&b[i]);
	while(l<r){
		int u=q[l++];
		if(u==0){
			printf("%d\n",dis[0]-1);
			return 0;
		}
		for(int i=1;i<=n;++i){
			int nxt=(1ll*a[i]*u+b[i])%m;
			if(!dis[nxt])dis[nxt]=dis[u]+1,q[r++]=nxt;
		}
	}
	puts("-1");
}