P8356 "WHOI-1" Sequence Counting

> No longer having it, the sequence stays with me.

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.

**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 $T$ lines, each line containing one non-negative integer, representing the answer for that test case.

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}$.** | $\texttt{Subtask}$ ID | Special Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $\sum n \leq 20$ | 10 | | 2 | $p \leq 10^3$ | 30 | | 3 | $xy, p$ are coprime | 10 | | 4 | None | 50 | 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