题目背景

题目描述

$t$ 组询问，每次询问给定正整数 $n,m$，计算

$$\prod_{a_1=1}^{m}\prod_{a_2=1}^{m}\cdots\prod_{a_n=1}^{m}\operatorname{lcm}(f_{a_1},f_{a_2},\dots,f_{a_n})\bmod{37426667} $$

的值。其中 $f_i$ 是斐波那契数，满足 $f_1=f_2=1$，且 $f_i=f_{i-1}+f_{i-2},\forall n\ge3$。

输入格式

第一行输入一个正整数 $t$ 表示询问组数。

接下来 $t$ 行，每行两个正整数 $n,m$ 表示一次询问。

输出格式

每次询问输出一行一个整数表示答案。

2
1 3
2 3

2
32

提示

样例解释

对于第一组询问，有答案为 $f_1f_2f_3=1\times1\times2=2$。

对于第二组询问，当 $a_1,a_2\in\{1,2\}$ 时 $\operatorname{lcm}(f_{a_1},f_{a_2})=1$，否则 $\operatorname{lcm}(f_{a_1},f_{a_2})=2$。故答案为 $2^5=32$。

数据范围与限制

本题采用捆绑测试，各 Subtask 的限制与分值如下。

Subtask No.	$t\le$	$n\le$	$m\le$	分值
$1$		$2$	$2 \times 10^3$	$13$
$2$	$5$	$2 \times 10^5$		$24$
$3$		$2 \times 10^7$	$2 \times 10^7$	$36$
$4$	$300$	$2 \times 10^{17}$		$27$

对于所有数据，满足 $1 \le t \le 300, 1 \le n \le 2 \times 10^{17}, 1 \le m \le 2 \times 10^7$。