这种数列满足下面这一条神奇的性质：
- a_0=0。
- \forall i\in[1,n] 均有 a_i=a {i-1}+x 或者 a_i=a {i-1}+y。
- \forall i\in[1,n],p \nmid a_i。
求这样的 {a}_0^{n} 的数量。答案对 10^9+7 取模。
两个数列不同，当且仅当他们有一个下标存储的元素不同。
这种数列满足下面这一条神奇的性质：
求这样的 {a}_0^{n} 的数量。答案对 10^9+7 取模。
两个数列不同，当且仅当他们有一个下标存储的元素不同。
一个输入文件包含多组数据。
第一行一个正整数 T 表示测试点数目。
接下来 T 行表示测试点。对于每组测试点，一行四个正整数，表示 n,p,x,y。
T 行，每行一个自然数表示该测试点的答案。
3 3 3 1 2 11 45 14 19 9876 10 114514 191981
2 1688 426554662
样例 #1：
这样的 a 有 [0,1,2,4],[0,2,4,5]。
样例 #2、#3：
本来可爱的 Otm 已经写好了上万页的样例解释了，但是更可爱的 miku 把它删掉了所以 Otm 不想再写一遍了。
对于所有测试数据，1\leq T\leq10^3,1\leq\sum n\leq10^4, 1\leq x,y,p\leq10^9，输入均为正整数。
WHOI