题目描述

已知立方和公式： $\\ 1^3+2^3+3^3+\cdots+n^3=(1+2+3+\cdots+n)^2$ $\\$给出正整数$n$,求$1$到$n$的立方和模9901的结果。

输入格式

一行，一个整数 $n$。

输出格式

一行，一个整数表示$1$到$n$的立方和模9901的结果。

样例 #1

样例输入 #1

10

样例输出 #1

3025

样例 #2

样例输入 #2

10000

样例输出 #2

7426

提示

数据范围及约定

• 对于 $70\%$ 的数据，$m \le 10^6$；
• 对于 $100\%$ 的数据，$m \le 10^9$。