Description

输入一个数字 N,计算 S = 1! + 2! + 3! + ... + N! 的末六位(不含前导 0), N! 表示 前N 个正整数之积.

Format

Input

输入数据有多组,每组包含一个正整数 N(N <= 106,) .

Output

对于每组输入,输出 S 的值.

Samples

10

37913

Hint