P11888 「Stoi2025」爱的飞行日记


$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 i\ge3$。

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

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

#### 样例解释 对于第一组询问，有答案为 $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$ | $1$ | $2$ | $2 \times 10^3$ | $13$ | | $2$ | $5$ | $2 \times 10^5$ | $2 \times 10^5$ | $24$ | | $3$ | $5$ | $2 \times 10^7$ | $2 \times 10^7$ | $36$ | | $4$ | $300$ | $2 \times 10^{17}$ | $2 \times 10^7$ | $27$ | 对于所有数据，满足 $1 \le t \le 300, 1 \le n \le 2 \times 10^{17}, 1 \le m \le 2 \times 10^7$。