#1782. 序列
序列
序列
题目描述
标题: 序列 - Problem - QOJ.ac
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