当前没有测试数据。

题目背景

XXs：***，我讨厌新运算，啊，你别过来，啊！

新运算：~~（伸出恶魔的双手，实则是鸭蛋

题目描述

XXs遇到了几道新运算的题目，由于XXs正在长脑子（睿智），所以他想请你帮帮他。

题型1：

$$\begin{vmatrix} \\ a & b \\ d & c \end{vmatrix} $$

解为：

$$ab^{\min(c, d)} \ - \ cd^{\min(a, b)}$$

保证：

$$1 \le a, b, c, d \le 10 ^{5} \\ 1 \le \min(a, b), min(c, d) \le 10 $$

题型2：

$$\sum_{i=m}^{n}$$

解为：

$$m + (m + 1) + (m + 2) + ... + (n - 1) + n$$

保证：

$$0 \le n < m \le 10^8$$

题型3：

$$k!$$

解为：

$$k \times (k - 1) \times (k - 2) \times ... \times 2 \times 1 $$

保证：

$$1 \le k \le 13$$

输入

多组数据输入，第一行输入一个正整数 $T \ (1\le T \le 10^{3})$，表示接下来要输入 $T$ 组数据，每组数据第一行输入一个正整数 $op$，表示新运算题目的种类。

当 $op = 1$，输入四个正整数 $a, b, c, d$。

当 $op = 2$，输两个非负整数数 $m, n$。

当 $op = 3$，输入一个正整数 $k$。

输出

多组数据输出，输出 $T$ 行，为每道新运算的答案，答案对 $114514$ 取模。

样例

3
1
1 1 1 1
2
0 1
3
2

0
1
2

提示

依题意。