#1782. 序列

    ID: 1782 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1401来源:qoj.ac数据:公开样例动态规划数学

序列

序列

题目描述

标题: 序列 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

称一个序列 (a1,a2,⋯,an) 是避免 120 模式的,当且仅当不存在 1≤i<j<k≤n 使得 ak<ai<aj。

给定质数 P。q 次询问,每次给定 n,m,求有多少个长度为 n 的、值域在 [0,m] 内的整数序列 a 是避免 120 模式的,结果对 P 取模。

输入格式

第一行两个整数 P,q,表示模数和询问次数。

接下来 q 行,每行两个整数 n,m,表示一组询问。

输出格式

输出共 q 行,第 i 行表示第 i 次询问的答案对 P 取模的结果。

样例数据

见下发文件。

数据范围

对于全部数据,满足 108≤P≤109,1≤q≤8×104,1≤n≤100,0≤m≤109。

测试点编号n≤m≤1,216163,418185,6181097,820209,102010911∼1610010017∼20100109

测试点 11∼20 关于 n 和 q 都有梯度。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

550226123 20
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
1
2
3
4
5
1
4
9
16
25
1
8
26
60
115
1
16
72
210
485

样例 2

543540857 10
6 0
1 0
2 1
9 5
5 0
2 1
11 2
11 1
1 0
12 5
1
1
4
978812
1
4
41472
2048
1
36477728