Grox的序列二¶
- 参考时间限制：0.5 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
- 参考评测环境与测量
背景故事¶
宇宙不是业余者适合去的地方。尽你所能学习一切，彻底抛弃你的偏见，然后行动。
——科学之书7（《Spore》，英文资料）
解决了第一道序列问题后，Grox 对你的专业水平十分满意。不过，上次对那些只能出现零次或奇数次的物质种类数限制得太紧了。别担心，Grox 自己也不会处理扩大范围后的问题。
他们在研究更大范围的解法时，发现了另一个有意思的序列。为了避免输出过多，Grox 只想知道它的三个汇总值。
形式化问题描述¶
令 \(P=1004535809\) .给定非负整数 \(n\) ，在模 \(P\) 意义下定义 Laurent 多项式（允许负整数指数的有限多项式）
\[
F_n(x)=\sum_{i=0}^{n}(i!)^{-1}x^i\sum_{j=0}^{n-i}(j!)^{-1}x^{-j}
\]
其中 \((i!)^{-1}\) 表示 \(i!\) 模 \(P\) 的乘法逆元，\(0!=1\) .把相同指数的项合并后，记 \([x^e]F_n(x)\) 为指数 \(e\) 的系数。
依次输出 \(A_0,A_1,A_2\) ，其中
\[
A_r=\sum_{\substack{-n\le e\le n\\e\equiv r\pmod3}}[x^e]F_n(x)\pmod P
\]
余数取 \(0,1,2\) ；例如指数 \(-1\) 属于余数 \(2\) .所有输出取 \(0\) 到 \(P-1\) 之间的代表元。
输入格式¶
一行一个整数 \(n\) .
输出格式¶
一行三个以空格分隔的整数 \(A_0,A_1,A_2\) .
样例 1¶
输入¶
1
输出¶
1 1 1
样例 2¶
输入¶
3
输出¶
334845272 2 2
样例 3¶
输入¶
0
输出¶
1 0 0
样例解释¶
当 \(n=1\) 时，\(F_1(x)=1+x+x^{-1}\) ，三个余数类别各有系数和 \(1\) .当 \(n=0\) 时只有常数项 \(1\) .
数据范围与保证¶
\(0\le n\le100000\) .\(P\) 为质数，\(P=479\cdot2^{21}+1\) ，\(3\) 是模 \(P\) 的原根。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |