Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

* When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.



To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

* 2 \leq N \leq 2 \times 10^5
* 1 \leq K \leq \min(N, 10)
* 1 \leq L_i \leq R_i \leq N
* [L_i, R_i] and [L_j, R_j] do not intersect (i \neq j)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
L_1 R_1
L_2 R_2
:
L_K R_K


Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Examples

Input

5 2
1 1
3 4


Output

4


Input

5 2
3 3
5 5


Output

0


Input

5 1
1 2


Output

5


Input

60 3
5 8
1 3
10 15


Output

221823067

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.util.Arrays; 
import java.util.ArrayList; 
import java.util.Collections; 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.StringTokenizer;
import java.math.BigInteger;
 
public class Main {
 
    public static void main(String[] args) {
        try (PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out))) {
            FastScanner in = new FastScanner(System.in);
            int n = in.nextInt();
            int k = in.nextInt();
            long mod = 998244353;
            
            ArrayList<Integer> lArray = new ArrayList<>();
            ArrayList<Integer> rArray = new ArrayList<>();
 
 
            for(int i = 0; i < k; i++) {
                int l = in.nextInt();
                int r = in.nextInt();
                lArray.add(l);
                rArray.add(r);        
            }
 
            long[] count = new long[n+1];
            long [] sum = new long[n+1];
 
            for(int i = 1; i < n+1; i++) {
                if(i == 1) {
                    count[i] = 1;
                    sum[i] = 1;
                    continue;
                }
 
                for(int j = 0; j < lArray.size(); j++) {
                    int l = lArray.get(j);
                    int r = rArray.get(j);
                    int sumStart = i - r;
                    int sumFinish = i - l;
 
                    if(sumFinish < 1) {
                        // out.println("here");
                        continue;
                    } else if(sumStart < 1) {
                        count[i] = (count[i] + sum[sumFinish])%mod;
                        continue;
                    }
                    count[i] = (count[i] + sum[sumFinish]-(sum[sumStart-1]))%mod;
                    // for(int m = lArray.get(j); m <= rArray.get(j); m++) {
                    //     if(i-m >=1) {
                    //         count[i] = count[i] + count[i-m];
                    //     } else {
                    //         break;
                    //     }
                    // }
                }
                sum[i] = (sum[i-1]+count[i])%mod;
            }
 
            out.println((count[n]+mod)%mod);
 
 
        } finally {
            //out.close();
        }
        
           
    }
}
 
 
class FastScanner {
   private final BufferedReader br;
   private StringTokenizer st;
 
    FastScanner(InputStream InputStream) {
        br = new BufferedReader(new InputStreamReader(InputStream));
    }
    
    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }
    
    int nextInt() {
        return Integer.parseInt(next());
    }
    
    long nextLong() {
        return Long.parseLong(next());
    }
    
    double nextDouble() {
        return Double.parseDouble(next());
    }
 
 
    
    ArrayList<Integer> nextIntList(int count) {
        ArrayList<Integer> array = new ArrayList<>();
        for (int n = 0; n < count; n++) {
            int number = nextInt();
            array.add(number);
        }
        return array;
    }
    
    int[] nextIntArray(int count) {
        int[] array = new int[count];
        for (int n = 0; n < count; n++) {
            array[n] = nextInt();
        }
        return array;
    }
}