F-简洁的题面_牛客练习赛87

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

求 $\sum\limits_{i_1=0}^n\sum\limits_{i_2=0}^n...\sum\limits_{i_k=0}^n\sum_{d=1}^g[d*(i_1+i_2+...+i_k)\le n]\prod_{j=1}^kC_{n-d*\sum_{h=1}^{j-1}i_h}^{d*i_j}$ ，答案对 ${P}$ 取模。

${[p]}$ ：当条件 ${p}$ 满足时为 ${1}$ ，否则为 ${0}$ 。

输入描述:

第一行一个整数，为测试用例的数量。
接下来行每行四个整数。

输出描述:

输出行，第行一个整数表示第组测试用例的答案。

示例1

输入

复制

2
5 1 998244353 1
5 2 998244353 2

输出

复制

32
304

备注:


不保证为素数。