Background

这是一道很好的对拍模板题😄

Description

有一个n*n的矩阵，请问它有多少个子矩阵？由于n很大，答案也会很大，你只需要输出答案的后6位就行啦（提示：可以mod 1000000）

Format

Input

n

Output

答案的后六位（不够用零占位）

Samples

2

000009

9

002025

999

250000

Limitation

• 样例一解释
• 左上角 右下角
• (1,1) (1,1)
• (1,2) (1,2)
• (2,1) (2,1)
• (2,2) (2,2)
• (1,1) (1,2)
• (2,1) (2,2)
• (1,1) (2,1)
• (1,2) (2,2)
• (1,1) (2,2)
• 共9个，前面占了5个0
• 20%的数据，$1≤n≤10^3$
• 60%的数据，$1≤n≤10^6$
• 100%的数据，$1≤n≤10^9$