# Grox的序列二

- 参考时间限制：0.5 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

> 宇宙不是业余者适合去的地方。尽你所能学习一切，彻底抛弃你的偏见，然后行动。
>
> ——科学之书7（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

解决了第一道序列问题后，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

### 输入

```text
1
```

### 输出

```text
1 1 1
```

## 样例 2

### 输入

```text
3
```

### 输出

```text
334845272 2 2
```

## 样例 3

### 输入

```text
0
```

### 输出

```text
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% | 无额外条件 |