Counting Permutations

Problem Description

When Tonyfang was studying monotonous queues, he came across the following problem: For a permutation of length n $a_1,a_2...a_n$, define $l_i$ as maximum x satisfying $x<i$ and $a_x>a_i$, or 0 if such x not exists, $r_i$ as minimum x satisfying $x>i$ and $a_x > a_i$, or n+1 if not exists. Output $\sum_{i=1}^n \min(i-l_i,r_i-i)$. Obviously, this problem is too easy for Tonyfang. So he thought about a harder version: Given two integers n and x, counting the number of permutations of 1 to n which $\sum_{i=1}^n \min(i-l_i,r_i-i)=x$ where l and r are defined as above, output the number mod P. Tonyfang solved it quickly, now comes your turn!

Input

In the first line, before every test case, an integer P. There are multiple test cases, please read till the end of input file. For every test case, a line contain three integers n and x, separated with space. $1 \leq n \leq 200, 1 \leq x \leq 10^9$. P is a prime and $10^8 \leq P \leq 10^9$, No more than 10 test cases.

Output

For every test case, output the number of valid permutations modulo P.

Sample Input

998244353

3 4

3 233

Sample Output

2

0

Source

2018 Multi-University Training Contest 2

https://acm.hdu.edu.cn/showproblem.php?pid=6310