该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

想遇见你，在某个小镇。

跑过街角，爬上树梢，飞过小巷。

躲上货架张望背影，围着行人脚边打转，随着歌声扭动尾巴，大摇大摆地擦肩而过。

浪花慵懒拍打着沙滩，夕阳小心地躺在屋顶。墙上的时光滴滴答答，从黎明到黄昏。

等待一次转身，等待与你的目光相遇。

遇见你的那一刻，崩坏的因缘再度牵系。

八十一个位面都为你闪烁。

题目描述

给定正整数 $n$ 和模数 $p$，你需要求出互不相同的元素总和为 $n$ 的单调不降正整数序列的个数。形式化地，你需要求出有多少个不同的正整数序列 $a$ 满足：

• 序列的长度 $m$ 在 $1$ 和 $n$ 之间（包括 $1$ 和 $n$）。
• 序列单调不降，即对于任意 $1 \le i<m$，$a_i\le a_{i+1}$。

输入格式

本题多测。

第一行输入两个正整数 $T,p$，分别表示测试数据组数和模数。

对于每组测试数据，输入一行一个正整数 $n$。

输出格式

对于每组测试数据输出一行一个整数，代表答案对 $p$ 取模的结果。

5 20250829
3
10
500
10000
100000

3
42
14351629
3506315
16068085

提示

样例解释

对于第一组测试数据，满足条件的序列分别是：$\{1,1,1\}$、$\{1,2\}$、$\{3\}$。

数据范围

对于 $100\%$ 的数据，保证 $1\le T,n\le 1.5\times10^5$，$2\le p \le10^9+9$。不保证 $p$ 是质数。