하와위시 복호화

하와위시는 이집트의 전통 음식이며, 워낙 귀하게 여겨져서 일부 사람들은 이것을 아주 튼튼한 금고에 보관한다. 금고는 다음 식에 따라 수열을 만드는 의사 난수 생성기로 보호된다.

$R_{n+1} = (a \times R_n + b) \bmod p$

여기서 $a$, $b$, $p$는 정수이고, $p$는 소수이다. $R_0$는 처음 생성되는 수이며, 수열의 시드(seed)라고 부른다.

시드는 $[A, B]$ 범위의 정수 중에서 무작위로 고른 값이다. 금고의 키 번호는 처음 생성되는 $N$개의 난수 $R_0, R_1, \cdots, R_{N-1}$ 중 하나로 나타나는 수이다. 여러 키 번호 $X$를 시험해 보기 전에, 먼저 $X$가 처음 $N$개의 난수에 나타날 확률을 구해야 한다.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 정수 $N$, $X$, $A$, $B$, $a$, $b$, $p$가 한 줄에 주어진다. ($1 \le N, X, A, B, a, b \le p - 1$, $1 < p < 10^8$, $1 \le A \le B \le \min(100, p - 1)$, $p$는 소수이다.)

각 테스트 케이스마다 $X$가 처음 $N$개의 생성된 수에 나타날 확률을 기약분수 $q/r$ ($q$, $r$은 정수) 꼴로 한 줄에 출력한다. 이 확률은 항상 기약분수로 나타낼 수 있다고 보장된다.

예를 들어 $a = 2$, $b = 1$, $p = 7$, $R_0 = 2$이면 생성되는 수는 $2, 5, 4, 2, 5, 4, 2, 5, 4, \cdots$이다. 마지막 두 테스트 케이스에서는 $a = 4$, $b = 7$, $p = 11$, $R_0 = 5$이므로 생성되는 수열은 $5, 5, 5, \cdots$이다.