Background

Under the blazing sun, I only want to hold an umbrella for you.
You lean on my shoulder, taking a deep breath, afraid you will forget.
Because of that silly fish-scooping game, we started talking.
I really hope the topics never end, and the carnival never closes.
A balloon in my hand, I hold yours and wander around.
I have something I want to tell you, but your eyes pretend to be busy.
I want to taste both the egg cakes and the jam at the corner of your lips.
The carnival video is playing; this world has agreed to wander together.
—— "Carnival"

Problem Description

Let $F(x)=(x+1)\bmod 3-1$. Given $n$, compute:

modulo $1732073999$. Here $C_{r}^{l}$ is a binomial coefficient, specifically:

Input Format

This problem has multiple queries.

The first line contains two positive integers $t,maxn$, representing the number of queries and the maximum possible value among the queries.

The next $t$ lines each contain one positive integer $n$.

Output Format

Output $t$ lines. The $i$-th line contains one integer: the answer to the $i$-th query modulo $1\ 732\ 073\ 999$.

4 173
1
5
20
34

3
12
52
94

Hint

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le t \le 3 \times 10^4,1 \le n \le maxn \le 2 \times 10^{16}$.

Translated by ChatGPT 5