T452322 背包装物品

有$n$种体积为$1$的物品和$m$种体积为$2$的物品，以及一个容量为$k$的背包（完全背包，每种物品数量无限） 求把背包恰好装满，有多少种方法？答案对质数$p$取模

第一行一个正整数$t$表示数据组数 接下来$t$行，每行四个数$n,m,k,p$

每组询问输出一行一个整数，表示答案

对于30%的数据，$k \le 10^5$。 对于60%的数据，$n, m \le 10^3，p \le 2 \times 10^4$。 对于100%的数据，$t \le 20，n, m \le 10^5，k \le 10^{12}，p \le 10^6$，保证$p$为质数。