34169번 - 경찰과 도둑 서브태스크

어린 시절 놀이터 혹은 학교에서 하던 경찰과 도둑, 일명 경도라고 불리는 놀이를 아는가? 안다면 당신도 이제 늙은 것이다.

어린 시절 즐겨하던 경도가 생각난 동우와 재우는 $2025$년 버전의 경찰과 도둑 게임을 하기로 했다.

이 게임을 진행하기 위해 우선 소수 $P$를 정한다. 게임은 $1$번부터 $P$번까지 번호가 붙은 $P$개의 도시에서 진행되며, 각 도시는 원형으로 배치되어 있다. $i(1\le i\le P-1)$번 도시 칸의 오른쪽에는 $i+1$번 도시 칸이 이웃해 있으며, $P$번 도시의 오른쪽에는 $1$번 도시가 이웃해 있다.

게임은 총 $N$턴으로 진행되며 처음에는 동우와 재우가 같은 도시 칸에 있다. 경찰 동우의 목표는 도둑 재우를 잡는 것이고, 반대로 도둑 재우의 목표는 경찰 동우에게 잡히지 않는 것이다. 각자 $N$턴의 행동을 한 후 동우와 재우가 같은 도시에 있다면 동우가 재우를 잡아 승리하고, 다른 도시에 있다면 재우가 승리한다.

게임은 동우의 상수 $X$, 재우의 상수 $Y$, 처음 시작하는 도시 $Z$를 정한 후 시작된다.

매 턴마다 동우와 재우는 선공 플레이어부터 다음 규칙에 따라 각자 움직인다. 한 턴 내 선공의 모든 움직임을 종료한 후 후공이 움직이기 시작하며, 후공까지 모두 움직여야 한 턴이 종료된다.

1. 먼저 플레이어가 현재 위치한 도시 칸에서 오른쪽 혹은 왼쪽 중 한 방향을 선택해 그 방향으로 한 칸씩 움직여 $1$번 도시 칸까지 움직인다. 이때 움직인 칸의 수를 $d$라 하자.
2. $1$번 도시에 도착을 했다면, 오른쪽 혹은 왼쪽 중 한 방향을 다시 선택해 그 방향으로 각자의 상수와 $d$를 곱한 만큼의 칸을 움직인다. 구체적으로 동우는 $X\cdot d$, 재우는 $Y\cdot d$만큼의 칸을 한 방향으로 움직인다.
3. 방향은 매 턴마다, 그리고 같은 턴의 두 번의 방향을 독립적으로 선택할 수 있다.

동우와 재우는 위의 규칙대로 모든 방향 선택을 랜덤하게 하여 정확히 $2$턴을 움직였을 때, 동우가 재우와 같은 도시에 있는 경우가 하나라도 존재할 수 있도록 하며, $1\le X,Y,Z\le P$를 만족하는 $\left( X,Y,Z \right)$ 중 하나를 동일한 확률로 뽑아 게임을 진행할 것이다.

동우와 재우는 정해진 세 정수 $\left( X,Y,Z \right)$와 턴 수 $N$, 도시의 수 $P$를 모두 알고 있다. 그러나 영악한 재우는 동우가 너무 유리할 것으로 생각하여 게임 시작 전 규칙을 바꾸었다. 원래 재우는 $Y\cdot d$칸을 이동했지만, 이제는 $\left( aY+b \right)\cdot d$칸을 이동한다고 통보한 것이다.

게임의 시작 전 선공을 정하며, 각자 상대방의 움직임을 볼 수 있는지 여부 또한 결정된다.

총 $T$개의 테스트 케이스에 대해 문제를 풀어야 한다. 각 테스트 케이스에는 도시의 수와 게임의 턴 수 $P$와 $N$, 그리고 선공 플레이어가 누구인 지 나타내는 $F$, 동우가 재우의 움직임을 볼 수 있는지 여부 $D$, 재우가 동우의 움직임을 볼 수 있는지 여부 $J$, 재우가 변환한 상수 $a$와 $b$가 주어진다. $F=1$이라면 동우가 선공, $F=0$이라면 재우가 선공이다. $D$ 혹은 $J$가 $1$이면 해당 플레이어는 매 턴 상대방의 움직임을 실시간으로 볼 수 있고, $D$ 혹은 $J$가 $0$인 사람은 게임이 종료될 때까지 상대방의 움직임을 볼 수 없다. 동우와 재우는 각자 본인이 승리하기 위해 최적으로 움직인다.

각 테스트 케이스 별로 동우가 게임에서 이길 확률을 계산해 보자.

첫 번째 줄에 $T(1\le T\le 10^5)$가 주어진다.

두 번재 줄부터 $T$개의 줄에 소수 $P(2\le P\le 10^{9})$, 정수 $N(0\le N\le 10^{18})$, $F$, $D$, $J(F,D,J\in\{0,1\})$, $a,b(1\le a,b\le P)$가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄씩 승리 확률을 출력하라.

• 조건을 만족하는 $\left( X,Y,Z \right)$가 하나도 없다면 -1을 출력한다.
• 확률이 $0$ 혹은 $1$이라면 각각 0 혹은 1을 출력한다.
• 확률이 $\frac{108}{124}$와 같이 정수가 아닌 유리수의 경우 27/31과 같이 기약 분수의 형태로 출력한다.