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.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int MOD = 998_244_353;
        
        final int N = sc.nextInt();
        final int K = sc.nextInt();
        
        final int[] L = new int[K];
        final int[] R = new int[K];
        
        for (int j = 0; j < K; j++) {
            L[j] = sc.nextInt();
            R[j] = sc.nextInt();
        }
        
        // マスidxに到達する方法の数を保持する。
        // 但しidxは0開始。
        final long[] dp = new long[N];
        dp[0] = 1;
        
        // dpの累積和を保持する。
        // つまり、sdp[n] = dp[0] + dp[1] + .. + dp[n]
        final long[] sdp = new long[N];
        sdp[0] = 1;
        
        // dp[1] .. dp[N - 1] を順に求める。
        for (int i = 1; i < N; i++) {
            
            for (int j = 0; j < K; j++) {
                if (R[j] < i) {
                    // dp[i] = dp[i - R] + dp[i - R + 1] + .. + dp[i - L - 1] + dp[i - L]
                    // である。
                    // ここで右辺について、
                    // dp[i - R] + dp[i - R + 1] + .. + dp[i - L - 1] + dp[i - L]
                    //   = dp[0] + dp[1] + .. + dp[i - R - 1] + dp[i - R] + dp[i - R + 1] + .. + dp[i - L - 1] + dp[i - L]
                    //   - dp[0] + dp[1] + .. + dp[i - R - 1]
                    //   = sdp[i - L] - sdp[i - R - 1]
                    // となる。
                    // まとめると、
                    //   dp[i] = sdp[i - L] - sdp[i - R - 1]
                    // これは区間jについてのみだから、実際にはそれぞれの区間jについて合計する。
                    dp[i] += sdp[i - L[j]] - sdp[i - R[j] - 1];
                    
                } else if (L[j] <= i) {
                    // dp[i] = dp[0] + dp[1] + .. dp[i - L - 1] + dp[i - L]
                    //       = sdp[i - L]
                    dp[i] += sdp[i - L[j]];
                    
                } else {
                    continue;
                }
                if (dp[i] < 0) {
                    dp[i] += MOD;
                } else {
                    dp[i] %= MOD;
                }
            }
            sdp[i] = sdp[i - 1] + dp[i];
            sdp[i] %= MOD;
        }
        
        System.out.println(dp[N - 1]);
    }
}