// Arup Guha
// 8/13/2026
// Solution to Kattis Problem: Modulo Solitaire
// https://open.kattis.com/problems/modulosolitaire

import java.util.*;

public class modulosolitaire {
	
	public static void main(String[] args) {
		
		// Read input.
		Scanner stdin = new Scanner(System.in);
		int mod = stdin.nextInt();
		int numMoves = stdin.nextInt();
		int s = stdin.nextInt();
		long[][] func = new long[numMoves][2];
		
		// Read all of the "moves"
		for (int i=0; i<numMoves; i++) 
			for (int j=0; j<2; j++)
				func[i][j] = stdin.nextInt();
		
		// Set up distance array for BFS.
		int[] dist = new int[mod];
		Arrays.fill(dist, -1);
		dist[s] = 0;
		
		// Set up queue for BFS.
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		q.offer(s);
		
		// Run BFS.
		while (q.size() > 0) {
		
			int cur = q.pollFirst();
			
			// Try each move.
			for (int i=0; i<numMoves; i++) {
				
				// Compute where we go using this move.
				long nxt = (func[i][0]*cur + func[i][1])%mod;
				
				// Been here before.
				if ( dist[(int)nxt] != -1) continue;
				
				// Mark distance and add to queue.
				dist[(int)nxt] = dist[cur]+1;
				q.offer( (int)nxt );
			}
		}
		
		// Ta da...
		System.out.println(dist[0]);
	}
}