# 八次求和
#### 问题描述
给定正整数 n, 求 1^8 + 2^8 +···+ n^8 mod 123456789 。其中 mod 表示取余。
#### 输入格式
输入的第一行包含一个整数 n。
#### 输出格式
输出一行，包含一个整数，表示答案。
#### 样例输入
```
2
```
#### 样例输出
```
257
```
#### 样例输入
```
987654
```
#### 样例输出
```
43636805
```
#### 评测用例规模与约定
对于 20% 的评测用例，1≤n≤20。
对于 60% 的评测用例，1≤n≤1000。
对于所有评测用例，1≤n≤1000000。

## aop
### before
```cpp

```
### after
```cpp

```

## 答案
```cpp

```
## 选项

### A
```cpp

```

### B
```cpp

```

### C
```cpp

```