問題文

非負整数 $x$ について、関数 $f(x)$ を次のように定めます。

• $f(0) = 1$
• $f(x) = f(x - 1) + x! \: (1 \leq x)$

$f(N)$ の値を $88888888$ で割った余りを求めてください。

制約

• $0 \leq N \leq 10^{9}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N

出力

問題の答えを一行に出力せよ。

入出力例

3

10

$f(1) = f(0) + 1! = 2$
$f(2) = f(1) + 2! = 4$
$f(3) = f(2) + 3! = 10$
であるので、$10$ を出力します。

100

66913826

$88888888$ で割った余りを出力することに注意してください。