P1040 The nflsM Tokens (HARD)

Problem Background

See problem P1039 The nflsM Tokens (EASY) (Fib3 Queue 2).

Problem Statement

Define \(F^{m}_{n}=F^{m}_{n-1}+F^m_{n-2}+\cdots+F^{m}_{n-m}\ (n\ge m),F^m_0=0,F^m_1=F^m_2=\cdots=F^m_{m-1}=1\) with \(m\ge2\).

Originally we have \(m=2\).

Given \(T\) queries. Each query is formatted like these below:

• 1 x means to make \(m\) equal \(x\).
• 2 n means to ask you to print \(F^m_n\) modulo \(998244353\) with the current \(m\).

Input

\(t\)
\(\text{Query}_1\)
\(\text{Query}_2\)
\(\text{Query}_3\)
\(\ \ \ \ \ \vdots\)
\(\text{Query}_t\)

For each query, it is formatted by two integers; more see problem statement.

Output

For each query with the \(2^{nd}\) operation, print the answer.

Constraints

• \(1 \le t \le 100\).
• For each query with the \(1^{st}\) operation, \(2 \le x \le 30\).
• For each query with the \(2^{nd}\) operation:
  • For \(20\%\) test cases: \(1 \le n \le 10^5\).
  • For all test cases: \(1 \le n \le 10^{9}\).

Samples

Input 1

7
2 10
1 3
2 5
1 10
2 11
1 2
2 5

Output 1

55
7
18
5