### 问题描述 晓宇发现了一种未知的基因，这种基因的结构十分的奇怪。只由 $2$ 种元素构成，为了表示方便，我们用 $0$ ，$1$ 来表示这两种元素。这断基因中可以出现任意的 $0$，$1$ 组合，但是绝对不会出现两个连续的 $1$ (例如：$1000101010$ 是合法的，$10101011$ 是非法的)。 现在你要解决的是，给定一个基因长度 ，请输出有多少种不同的基因排列方法（长度为 $0$ 排方法为 $0$ ）。 ### 输入格式 第一排一个数 $N$ 表示有 $N$ 个询问。以下 $N$ 排每排一个数 $K$ ，表示询问长度为 $K$ 的基因有多少种不同的组合方式。 ### 输出格式 输出 $N$ 排，每排对应一个询问。答案对 $12345$ 取余。 ### 样例输入 ``` 2 1 2 ``` ### 样例输出 ``` 2 1 2 ``` ### 评测数据范围 对于 $30\\%$ 的数据，保证 $n \le 1000$ 。 对于 $60\\%$ 的数据，保证 $n \le 10000$ 。 对于 $100\\%$ 的数据，保证 $0 \lt n \le 1000000, k \lt 100000$ 。