Background

A problem by CYJian after multiple rounds of strengthening.

Problem Description

Given $A, B$, find the value of the following expression:

$$\prod_{i=A}^{B}\prod_{j=1}^{i}\left(\frac{i}{j}\right)^{\left\lfloor \frac{i}{j} \right\rfloor}\bmod 19260817$$

There are $T$ queries.

---

It is said that many people cannot understand the formula.

Alright, here is the pseudocode:

for i = A to B
  for j = 1 to i
    res = res * power(i / j, floor(i / j))
res = solve(res)

The final solve means converting it into the form of a fraction modulo.

It is not guaranteed that the precision will not blow up on the spot.

Input Format

The first line contains a positive integer $T$.

The next $T$ lines each contain two positive integers, representing $A, B$ for this query.

Output Format

Output $T$ lines. Each line contains one positive integer, the answer for that query.

1
1 3

162

Hint

Sample explanation: $1 \times 4 \times 1 \times 27 \times \frac{3}{2} \times 1 \equiv 162 \pmod{19260817}$.

This problem uses bundled tests.

Constraints	$T =$	$A \le B \le$
$1 \sim 5$	$1$	$5000$
$6 \sim 10$		$10^6$
$11 \sim 15$	$10^6$	$5000$
$16 \sim 20$		$10^6$

Translated by ChatGPT 5