题目描述

给定一个正整数 $n$，定义

$$S(n)=1^1+2^2+3^3+\cdots+n^n.$$

请计算

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

也就是说，你需要输出 $1^1+2^2+\cdots+n^n$ 除以 $1000036000099$ 后的余数。

已知

$$1000036000099=1000003\times 1000033.$$

输入格式

输入一行一个整数 $n$。

输出格式

输出一行一个整数，表示

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

数据范围

$$1\le n\le 10^{18}.$$

样例 1

3

32

样例 2

10

10405071317

说明

对于样例 1：

$$1^1+2^2+3^3=1+4+27=32.$$