No testdata at current.

Background

土拨鼠文景刚刚学习了等比数列. 等比数列_百度百科

Description

文景给了你q次询问，每一次询问有两种类型：

• 1 a q n表示让你求一个第一项为$a$，公比为$q$，长度为$n$的等比数列，所有项加起来的和 $mod \ 998244353$是多少。
• 2 a q m表示让你求一个第一项为$a$，公比为$q$的等比数列，第m项 $mod \ 998244353$是多少。

Format

Input

第一行一个整数，q。后面q行，每行四个整数（见题目说明）。

Output

对于1询问和2询问，输出一个整数表示结果。

Samples

2
1 1 2 3
2 1 2 4

7
8

Limitation

$1≤q≤10^4$，$1≤每次询问中出现的整数≤10^9$

1s, 1024KiB for each test case.