时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小y现在有一个神奇的盒子。盒子里面有红蓝两种卡片。每种卡片都有n张，其中第i张上的数字为
。小y想从盒子中取出一些卡片。使得这些卡片的和为m。他想知道有多少种方案。
小k又觉得此题太水，所以出题人只好又加强了一下。
现在你需要将m从1枚举到S，S为盒子中所有卡片数字之和。问所有方案之和。
也就是说设f(m)表示取出的卡片数字之和为m的方案数。你需要求)
由于答案可能巨大，你需要输出答案对P取模的结果
小k又觉得此题太水，所以出题人只好又加强了一下。
现在你需要将m从1枚举到S，S为盒子中所有卡片数字之和。问所有方案之和。
也就是说设f(m)表示取出的卡片数字之和为m的方案数。你需要求
由于答案可能巨大，你需要输出答案对P取模的结果
输入描述:
第一行一个正整数T。表示数据组数
然后2n行每行一个正整数n，P交替。表示卡片的个数和模数
输出描述:
输出共T行。每行一个正整数。
第i行表示第i组数据的答案。