Time Limit: 3s → 6s
本题中,对于一个无重边自环的无向图,称图上的一条道路为简单路当且仅当其不经过重复节点。即,假设该道路经过的节点依次为 (u1,u2,⋯,uk),则这条道路为简单路当且仅当 u1,u2,⋯,uk 两两不同。
给出大质数 P 和 q 次询问,每组询问给出正整数 n,你需要求出满足以下所有条件的有标号无向图个数,对 P 取模:
- 图有 n 个节点且不存在重边与自环;
- 图上不存在边数为 3 的简单路,即图上无法找到四个两两不同的节点 u1,u2,u3,u4 满足 (u1,u2),(u2,u3),(u3,u4) 均在图中;
- 在满足条件 1 和 2 的基础上,图的边数最多。
输入格式
输入的第一行包含两个正整数 q, P,保证 q≤105,分别表示询问次数和模数。
接下来 q 行每行包含一个正整数 n,保证 n≤3×107,描述一次询问。
输出格式
对于每组询问输出一行一个非负整数,表示满足条件的有标号无向图个数对 P 取模的值。
样例数据
样例输入
2 199932539
1
6
样例输出
1
10
样例解释
以下样例解释将用 1 到 n 之间的整数给每个节点进行编号。
对于第一组询问,只有边集为 ∅ 的图满足条件。
对于第二组询问,其中两个满足条件的图的边集分别为 {(1,2)(2,3)(1,3)(4,5)(5,6)(4,6)} 和 {(1,3)(3,5)(1,5)(2,4)(4,6)(2,6)}。
子任务
对于全部数据,保证 108<P<109 且 P 是素数。
子任务编号 | n≤ | q≤ | 分值 |
---|---|---|---|
1 | 8 | 8 | 20 |
2 | 200 | 200 | 15 |
3 | 3000 | 3000 | 15 |
4 | 5×105 | 105 | 20 |
5 | 3×107 | 30 |