Product of LCMs of Fibonacci Numbers

You are given t queries. In each query, you are given two positive integers n and m. Let \(f_i\) be the Fibonacci numbers defined by \(f_1 = f_2 = 1\) and \(f_i = f_{i-1} + f_{i-2}\) for all \(i\ge3\). For a fixed query, consider all \(n\)-tuples \((a_1,a_2,\dots,a_n)\) where each \(a_i\) is an integer between 1 and m (inclusive). For each tuple, compute the least common multiple (LCM) of \(f_{a_1}, f_{a_2}, \dots, f_{a_n}\). Your task is to compute

[ P = \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, ]

for each query.

Note: Although directly iterating over all \(m^n\) tuples is infeasible, the problem can be solved by using the prime factorization of Fibonacci numbers. For any prime \(p\), if we denote \(v_p(f_i)\) as the exponent of \(p\) in \(f_i\), then for a given tuple, the exponent contributed by \(p\) is \(\max\{v_p(f_{a_1}),v_p(f_{a_2}),\dots,v_p(f_{a_n})\}\). By counting the frequency of each exponent among \(f_1, f_2, \dots, f_m\), one may compute the sum of maximum exponents over all tuples and then combine the contributions of all primes.

inputFormat

The first line contains an integer t indicating the number of queries. Each of the following t lines contains two positive integers n and m separated by a space.

outputFormat

For each query, output a single line containing the value of \(P\) modulo \(37426667\).

sample

1
1 1

1