称一个序列 $ (a_1,a_2,\cdots,a_n) $ 是避免 120 模式的，当且仅当不存在 $ 1\leq i<j<k\leq n $ 使得 $ a_k<a_i<a_j $。
给定质数 $ P $。$ q $ 次询问，每次给定 $ n,m $，求有多少个长度为 $ n $ 的、值域在 $ [0,m] $ 内的整数序列 $ a $ 是避免 120 模式的，结果对 $ P $ 取模。
输入格式
第一行两个整数 $ P,q $，表示模数和询问次数。
接下来 $ q $ 行，每行两个整数 $ n,m $，表示一组询问。
输出格式
输出共 $ q $ 行，第 $ i $ 行表示第 $ i $ 次询问的答案对 $ P $ 取模的结果。
样例数据
见下发文件。
数据范围
对于全部数据，满足 $ 10^8\leq P\leq 10^9 $，$ 1\leq q\leq 8\times 10^4 $，$ 1\leq n\leq 100 $，$ 0\leq m\leq 10^9 $。
| 测试点编号 | $ n\leq $ | $ m\leq $ |
|---|---|---|
| $ 1,2 $ | $ 16 $ | $ 16 $ |
| $ 3,4 $ | $ 18 $ | $ 18 $ |
| $ 5,6 $ | $ 18 $ | $ 10^9 $ |
| $ 7,8 $ | $ 20 $ | $ 20 $ |
| $ 9,10 $ | $ 20 $ | $ 10^9 $ |
| $ 11\sim 16 $ | $ 100 $ | $ 100 $ |
| $ 17\sim 20 $ | $ 100 $ | $ 10^9 $ |
测试点 $ 11\sim 20 $ 关于 $ n $ 和 $ q $ 都有梯度。