#525. 「LibreOJ β Round #4」多项式

内存限制:256 MiB 时间限制:100 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: qmqmqm

题目描述

给定一个正整数 kk,你需要寻找一个系数均为 00k1k-1 之间的非零多项式 f(x)f(x),满足对于任意整数 xx 均有 f(x)modk=0f(x) \bmod k=0。你给出的多项式次数不能超过 6000060000,且最高次系数必须非 00

输入格式

输入一行,包含一个正整数 kk

输出格式

若无解,则只输出一个整数 1-1。否则首先输出一个整数 nn 表示你寻找的多项式的次数,随后 n+1n+1 个整数按照从低位到高位的顺序输出多项式的系数。

在此之后的输出将被忽略。

样例

样例输入

3

样例输出

4
0 1 2 2 1

样例解释

多项式为 x4+2x3+2x2+xx^4+2x^3+2x^2+x

数据范围与提示

1k300001 \leq k \leq 30000