题目背景

我顶着大太阳 只想为你撑伞
你靠在我肩膀 深呼吸怕遗忘
因为捞鱼的蠢游戏我们开始交谈
多希望话题不断园游会永不打烊
气球在我手上 我牵着你瞎逛
有话想对你讲 你眼睛却装忙
鸡蛋糕跟你嘴角果酱我都想要尝
园游会影片在播放 这个世界约好一起逛
——《园游会》

题目描述

设 $F(x)=(x+1)\bmod 3-1$，给定 $n$，求：

对 $1732073999$ 取模。其中 $C_{r}^{l}$ 为组合数，具体地，

输入格式

本题有多组询问。

第一行两个正整数 $t,maxn$，表示询问组数与询问的最大可能值。

接下来 $t$ 行，每行一个正整数 $n$。

输出格式

共 $t$ 行，第 $i$ 行一个整数，为第 $i$ 次询问的答案对 $1\ 732\ 073\ 999$ 取模的结果。

4 173
1
5
20
34

3
12
52
94

提示

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，$1 \le t \le 3 \times 10^4,1 \le n \le maxn \le 2 \times 10^{16}$。