Background

No longer having it, the sequence stays with me.

Problem Description

This kind of sequence satisfies the following magical property:

• $a_0 = 0$.
• $\forall i \in [1,n]$, we have $a_i = a_{i-1} + x$ or $a_i = a_{i-1} + y$.
• $\forall i \in [1,n], p \nmid a_i$.

Find the number of such $\{a\}_0^{n}$. Output the answer modulo $10^9+7$.

Two sequences are different if and only if there exists an index where the stored element is different.

Input Format

One input file contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines describe the test cases. For each test case, one line contains four positive integers, denoting $n, p, x, y$.

Output Format

Output $T$ lines, each line containing one non-negative integer, representing the answer for that test case.

3
3 3 1 2
11 45 14 19
9876 10 114514 191981

2
1688
426554662

Hint

Sample #1:

Such $a$ are $[0,1,2,4], [0,2,4,5]$.

Sample #2 and #3:

The originally cute Otm has already written tens of thousands of pages of sample explanations, but the even cuter miku deleted them, so Otm does not want to write them again.

This problem uses the $\texttt{Subtask}$ scoring method. You can get the score of a $\texttt{Subtask}$ only if you pass all test cases in that $\texttt{Subtask}$.

For all testdata, $1 \leq T \leq 10^3$, $1 \leq \sum n \leq 10^4$, $1 \leq x,y,p \leq 10^9$. All inputs are positive integers.

Translated by ChatGPT 5