这种数列满足下面这一条神奇的性质：

• 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 取模。

两个数列不同，当且仅当他们有一个下标存储的元素不同。

一个输入文件包含多组数据。

第一行一个正整数 T 表示测试点数目。

接下来 T 行表示测试点。对于每组测试点，一行四个正整数，表示 n,p,x,y。

T 行，每行一个自然数表示该测试点的答案。

样例 #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