//Jackson Simoneau
//COP 3503H - Fall 2026
//K3: Modulo Solitaire

import java.util.*;
public class modulosolitaire {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long m = input.nextLong();
        int n = input.nextInt();
        long s = input.nextLong();

        long[] a = new long[n], b = new long[n];
        for(int i = 0; i < n; i++) {
            a[i] = input.nextLong();
            b[i] = input.nextLong();
        }
        
        //initialize distance array and queue
        int[] dist = new int[(int)(m)];
        for(int i = 0; i < m; i++) dist[i] = -1;
        dist[(int)(s)] = 0;
        
        Queue<Long> q = new LinkedList<>();
        q.add(s);

        //run the BFS
        while(!q.isEmpty()) {
            long u = q.remove();
            for(int i = 0; i < n; i++) {
                //compute the new value if index i is chosen
                long v = (a[i]*u + b[i]) % m;
                //add this to the queue if unvisited
                if(dist[(int)(v)] == -1) {
                    dist[(int)(v)] = dist[(int)(u)] + 1;
                    q.add(v);
                }
            }
        }
        System.out.println(dist[0]);
    }
}