SP8423 BTCODE_E - Recover Polynomials

Venkatesh 是个精通数学的人，喜欢在空闲时研究多项式。他最钟爱的方程式是：$f(x) = a_n \cdot x^n + a_{n-1} \cdot x^{n-1} + \dots + a_1 \cdot x + a_0$。他有个朋友叫 Suhash，总喜欢给他出难题。在一次聚会中，他们讨论到一个有趣的问题： Suhash 会选定一个整数 $n$ 作为多项式的最高次幂，并给 Venkatesh 提供这个多项式在 $n+1$ 个等距离点上的值。具体来说，他给出三个整数 $n$、$x_0$ 和 $d$，以及一系列整数 $g_0, g_1, g_2, \dots, g_n$，满足：$f(x_0) = g_0, f(x_0 + d) = g_1, f(x_0 + 2 \cdot d) = g_2, \dots, f(x_0 + n \cdot d) = g_n$。现在，Venkatesh 需要找出这个多项式。由于他不喜欢处理浮点数，所以他打算以整数系数的形式来解出多项式，并且对一个质数取模。你能帮助他找到吗？

首先输入一个整数 $t$ 表示测试用例的数量。 对于每个测试用例，第一行为三个空格分隔的整数 $n, x_0, d$。接下来一行为 $n+1$ 个空格分隔的整数 $g_0, g_1, g_2, \dots, g_n$。

对于每个测试用例，输出多项式的 $n+1$ 个系数 $a_0, a_1, a_2, \dots, a_n$。输出的所有系数均为非负整数且小于 $1000000007$。 你需要找出满足以下等式的多项式系数 $a_0, a_1, a_2, \dots, a_n$： $$f(x_0) \equiv g_0 \pmod{1000000007}, f(x_0 + d) \equiv g_1 \pmod{1000000007}, \dots, f(x_0 + n \cdot d) \equiv g_n \pmod{1000000007}$$ 题目保证每个测试用例的解都是唯一的。

- $1 \le t \le 100$ - $1 \le n \le 100$ - $0 \le x_0, d \le 10^9$ - $0 \le g_i < 1000000007$ **本翻译由 AI 自动生成**