假设您有两个多项式 $$A(x) = \sum_{k=0}^{n} a_k x^k$$ 和 $$B(x) = \sum_{k=0}^{m} b_k x^k$$。那么多项式$$A(x)$$可以通过以下方式唯一表示:
$$A(x) = B(x) \cdot D(x) + R(x), \deg R(x) < \deg B(x).$$
这可以使用长除法来完成。这里,$$\deg P(x)$$表示多项式P(x)的次数。 $$R(x)$$称为多项式$$A(x)$$除以多项式$$B(x)$$的余数,也记为$$A \bmod B$$。
由于有一种方法可以将多项式除以余数,因此我们可以定义欧几里得算法来查找两个多项式的最大公约数。该算法采用两个多项式$$(A,B)$$。如果多项式 $$B(x)$$ 为零,则结果为 $$A(x)$$,否则结果为算法为 $$( B, A \bmod B )$$ 对返回的值。在每一步中,第二个参数的次数都会减少,因此该算法以有限数量的步骤运行。但这个数字有多大呢?你要回答这个问题。
给定一个整数 n。您必须建立两个次数不大于 n 的多项式,使得它们的系数是绝对值不超过 1 的整数,前导系数(具有最大 x 次方的系数)等于 1,并且所描述的欧几里得算法恰好执行 n 个步骤来查找其最大公约数。此外,第一个多项式的次数应大于第二个多项式的次数。算法的一步是指从 $$(A,B)$$ 到 $$( B, A \bmod B )$$ 的转换。
输入
给您一个整数 n (1 ≤ n ≤ 150) — 您需要达到的算法步骤数。
输出
按以下格式打印两个多项式。
在第一行中打印一个整数 m (0 ≤ m ≤ n) — 多项式的次数。
在第二行中打印 m + 1 个介于 - 1 和 1 之间的整数 — 多项式的系数,从常数到前导。
第一个多项式的次数应大于第二个多项式的次数,前导系数应等于 1。当使用这些多项式调用时,欧几里得算法应恰好执行 n 个步骤。
如果给定的 n 没有答案,则打印 -1。
如果有多个答案,则打印其中任何一个。
示例
输入 #1
1
输出 #1
1 0 1 0 1
输入 #2
2
输出 #2
2 -1 0 1 1 0 1
注意
在第二个示例中,您可以打印多项式 x2 - 1 和 x。转换的顺序是
(x2 - 1, x) → (x, - 1) → ( - 1, 0)。
其中有两个步骤。