P7976 "Stoi2033" Carnival

> 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"

Let $F(x)=(x+1)\bmod 3-1$. Given $n$, compute: $$\sum_{l=0}^n \sum_{r=l}^n F\left(C_{r}^{l}\right)$$ modulo $1732073999$. Here $C_{r}^{l}$ is a binomial coefficient, specifically: $$C_{r}^{l}=\dfrac{r!}{l!(r-l)!}$$

**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 $t$ lines. The $i$-th line contains one integer: the answer to the $i$-th query modulo $1\ 732\ 073\ 999$.

### Constraints **This problem uses bundled testdata.** | Subtask | Score | $1\le t \le$ | $1\le n \le maxn \le$ | | :-: | :-: | :-: | :-: | | $1$ | $16$ | $1$ | $300$ | | $2$ | $37$ | $300$ | $7 \times 10^6$ | | $3$ | $47$ | $3 \times 10^4$ | $2 \times 10^{16}$ | 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