自古枪兵幸运E
题目描述
俗话说，自古枪兵幸运E。而身为幸运E的L叔最想要的，就是C妈的金
羊毛了。然而这显然不是那么容易达成的。为了防止入侵者，C妈花费了k单位
魔力，建造了包含了若干个消耗一单位魔力的小型防御设施和消耗两单位魔力的
大型防御设施。
经过很长时间的调查，L叔终于了解到了C妈可能采用的小型防御设施有n
种，大型防御设施有m种。每一种都可以建造任意个数个。由于L叔拥有Rune
文字的加持和B级别的对魔力，只要了解每一种防御设施的数量，就可以破解
这样的防御。
然而，因为L叔的幸运是E，所以他只有在尝试每一种方案之后才能找到破
解的方法。他找到你，想让你判断一下他要尝试多少次才找到破解方法。由于凯
尔特神话中对数字的迷信，你只要输出答案模p的值就可以了。
输入格式
第一行一个正整数t，表示数据组数。
接下来t行每行四个非负整数n,m,k,p。
输出格式
t行每行一个整数，表示答案模p的值。
3
0 10 2 47
2 2 4 47
5 5 10 47
10
14
6
数据范围与约定
对于100%的数据，t ≤ 20，n, m ≤ 10^5，k ≤ 10^12，p ≤ 10^6，p 为质数。