기체와 쿼리

원이는 변형되지 않는 직육면체 모양의 실험 기구를 가지고 있다.

원이는 이 실험 기구를 한 면에 평행한 단면으로 $N$등분하고, 각각의 인접한 칸을 구분하는 고체 칸막이를 $N-1$개 설치했다. 초기에 실험 기구는 진공 상태이다.

이제 원이는 칸 $N$개와 칸막이 $N-1$개에 대해 아래와 같은 작업을 반복해 수행할 것이다. 칸막이를 제거하더라도 칸의 번호는 바뀌지 않음에 유의하라.

1. $X$번 칸과 $X+1$번 칸 사이의 칸막이를 제거한다.
2. $X$번 칸과 $X+1$번 칸 사이에 칸막이를 설치한다.
3. $X$번 칸에 기체를 $Y$ mol 주입한다.
4. $X$번 칸에 들어 있는 기체의 양을 mol 단위로 구한다.

또한 다음을 가정하자.

• 칸막이는 기체에 의해 움직이지 않는다.
• 칸막이로 구분된 칸 사이로는 기체가 드나들 수 없으며, 그렇지 않은 칸 사이로는 자유롭게 이동할 수 있다.
• 칸막이로 구분되지 않은 두 개 이상의 칸이 있을 때, 연결된 칸 각각의 기체 양은 동일하다.

원이는 위 작업을 시뮬레이션할 놀라운 방법이 떠올랐으나, 시험 공부를 하느라 PS를 게을리 했기 때문에 구현을 할 줄은 모른다. 여러분이 원이를 도와 이 작업을 구현해 주자.

첫째 줄에 칸막이의 개수 $N$과 작업의 횟수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 100~000$, $1 \leq Q \leq 100~000$)

둘째 줄부터 $Q$개의 줄에 위 형식에 따라 작업 $Q$개가 한 줄에 하나씩 주어진다.

물론 한 쿼리에 포함되는 값들은 모두 한 줄에 공백을 사이에 두고 주어진다.

입력되는 모든 수는 정수이다.

4번 작업이 주어질 때마다 답을 아래와 같이 정수로 구한 뒤 한 줄에 하나씩 출력한다.

4번 작업의 답은 항상 유리수임을 증명할 수 있다. 4번 작업이 주어지면, 이 유리수가 기약분수로 $\frac P Q$라 할 때, $P = R \times Q$ (mod $998~244~353$)인 $0$ 이상 $998~244~353$ 미만의 정수 $R$을 대신 구한다. 이러한 $R$이 유일하게 존재하는 입력만 주어짐을 보장한다.

$998~244~353$은 소수이다.

이 문제를 해결하는 데 사용할 수 있는 페르마 소정리의 내용은 다음과 같다.

임의의 소수 $p$와 정수 $a$에 대해 항상 다음 식이 성립한다.

$a ^ {p-1} \equiv 1$ (mod $p$)

또한 지수를 비트로 표현해 빠르게 수를 거듭제곱할 수 있다. 재귀적으로 $a^1$, $a^2$, $a^4$, ...을 계산한 뒤 이들 중 일부 또는 전부의 곱으로 주어진 거듭제곱을 표현하면 된다.