题目描述

我们一次又一次地试图接纳它们，无论这要付出何等的代价，我们必须理解！！！

We incessantly tried to accept it. We wanted to understand them in our heads by any means, regardless of the consequences.

紫罗兰色午夜降临，数个石碑群展现出了神明的迷思的样貌，作为一名员工，小 D 的任务是解析并理解这些石碑上碑文的含义。

小 D 发现，每座石碑的碑文都是一个整数序列，且碑文的第一个整数 $n$ 总表示该碑文在此之后的整数的数量。换言之，每段碑文可以表示成 $n+1$ 个整数 $n,a_0,a_1,a_2,\dots,a_{n-1}$，且它们在 $0$ 到 $10006$ 之间（包含两端）。如果把后 $n$ 个数看作一个 $n-1$ 次多项式 $\displaystyle f(x) = \sum_{i=0}^{n - 1}a_i \cdot x^i$ 的 $n$ 个系数，则碑文的真正含义就是同余方程 $f(x)\equiv 0\ (\mathrm{mod}\ 10007)$ 在 $x\in[0,10006]\cap\mathbb{N}$ 上的根的和，再对质数 $10007$ 取模的结果。请注意，即使出现重根，你仍须单独计算每一重。即，你需要计算 $\displaystyle \left(\sum_{x=0}^{10006}x\cdot c_f(x)\right)\mathrm{mod} \ 10007$，其中 $c_f(x)$ 表示 $x$ 在多项式 $f$ 中的重根数，若 $x$ 不是 $f$ 的根，则 $c_f(x)=0$。

你需要解析多段独立的碑文，为了保证碑文能以正确的顺序被解析，本题要求强制在线，即会使用下述加密规则使用上一段碑文的答案对下一段碑文进行加密：

对于第 $t$ 段碑文，记上一段碑文，即第 $t-1$ 段碑文的答案为 $ans_{t-1}$，记此前所有碑文答案的和，即 $ans_0,ans_1,\dots,ans_{t-1}$ 的和为 $sum_{t-1}$。我们规定 $ans_0 = 1，sum_0 = 1$。

每段碑文的 $n+1$ 个整数 $n,a_0,a_1,a_2,......a_{n-1}$，我们会通过

$$\begin{cases} n'= \left( n \cdot ans_{t-1}+sum_{t-1} \right) \mathrm{mod} \ 10007 \\ a_i'= \left( a_i \cdot ans_{t-1}+sum_{t-1} \right) \mathrm{mod} \ 10007 \end{cases} $$

对其进行加密，并给出加密后的 $n',a_0',a_1',a_2',\dots,a_{n-1}'$，而你需要将输入利用该规则进行解密，才能得到真正 $n,a_0,a_1,a_2,\dots,a_{n-1}$。

当你发现解密后的碑文为 $n=1,a_0=0$，则表示这是最后一段碑文，并且对于这段碑文你不需要输出任何答案。

现在利用 TIME TRACK II 协议，你同时得到了所有加密后的碑文，请据此帮小 D 解析出除最后一段碑文外所有碑文的答案。

输入格式

输入包含多行，每行包含若干个整数 $0 \leq n',a_0',a_1',a_2',......a_{n-1}'\leq 10006$，表示一段加密后的碑文。

保证输入不超过 $200$ 行，且最后一行有 $n=1,a_0=0$。

输出格式

对于除最后一段的每一段碑文，请输出一行包含一个整数，表示该段碑文的答案。

6 1 8144 3263 8377 234
22 8384 1639
12 475 9317 242
27 12 4427 9798 5126 711
33 8395 1650
21 20

7
1
3
7
1