暂无测试数据。

题目背景

\(\sf\pink{\sf 2024hyx}\) 在梦中见到了一个神秘人，神秘人说：“给你一个问题，如果回答不出来，你就会被永远困在梦境中，哈哈哈！！！”

题目描述

定义斐波契契数列 \(F\) 为：

\[F_1=F_2=1,\]

\[F_i=\prod^{i-2}_{j=1}(F_j+1)（i>2）.\]

你需要求出它的第 \(k\) 项。

结果可能非常大，你只需输出对结果模 \(10^9+129\) 值即可。

输入格式

本题采用多组数据。

第一行，一个数 \(T\)，代表数据组数。

接下来 \(T\) 行，每行一个数，代表 \(k\)。

输出格式

共 \(T\) 行。

对于每组数据。一行，输出一个数，代表答案。

样例 #1

样例输入 #1

5
1
5
100
10000
1000000

样例输出 #1

1
12
669354396
194792154
781552373

提示

本题采用测试点捆绑。

数据范围：

Subtask #0 （10分）：\(1 \le T \le 10,1 \le k \le 10\)。

Subtask #1 （20分）：\(1 \le T \le 10^5,1 \le k \le 10^7\)。

Subtask #2 （70分）：\(1 \le T \le 10^5,1 \le k \le 10^{18}\)。

因为这是，所以请你忽略以上分值。