#P9520. Sum the Series

    ID: 6103 传统题 3000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>CF2100提高中国剩余定理费马小定理等比数列求和逆元线性递推快速幂

Sum the Series

题目描述

给定一个正整数 nn,定义

S(n)=11+22+33+⋯+nn.S(n)=1^1+2^2+3^3+\cdots+n^n.

请计算

S(n) mod 1000036000099.S(n)\bmod 1000036000099.

也就是说,你需要输出 11+22+⋯+nn1^1+2^2+\cdots+n^n 除以 10000360000991000036000099 后的余数。

已知

1000036000099=1000003×1000033.1000036000099=1000003\times 1000033.

输入格式

输入一行一个整数 nn。

输出格式

输出一行一个整数,表示

$$\left(\sum_{x=1}^{n}x^x\right)\bmod 1000036000099.$$

数据范围

1≤n≤1018.1\le n\le 10^{18}.

样例 1

3
32

样例 2

10
10405071317

说明

对于样例 1:

11+22+33=1+4+27=32.1^1+2^2+3^3=1+4+27=32.