Processing math: 100%
Restricted path - MarisaOJ: Marisa Online Judge

Restricted path

Time limit: 1000 ms
Memory limit: 256 MB
Given an n×n grid, there are q queries. Each query is of the form (x,y), where x≤y. Starting from cell (x,y), you can move from cell (i,j) to cells (i+1,k) and j≤k≤n. However, you cannot move to cells with coordinates (a,b) where a>b. Determine the number of ways to reach (n,n) from (x,y). ### Input - The first line contains two integers n,q. - The next q lines, each containing two integers x,y, representing a query. ### Output - For each query, print an integer representing the number of paths modulo 998244353 from (x,y) to (n,n). ### Constraints - 1≤n,q≤105. - 1≤x≤y≤n. ### Sample test Input 53241113 Output: 3149