Background

春天来了, JP的季节到了~

Description

土拨鼠有若干个部落, 为了防止近亲结婚, 一个部落的土拨鼠只能与其他部落的土拨鼠结婚.

现在有n个部落, 每个部落有1个男鼠和1个女鼠外出搞对象.

问共有多少种JP方案.

Format

Input

一个整数n, 表示部落数量.

Output

可能的JP方案总数. 结果对$10007$求模.

Samples

3

2

样例解释

A,B,C三个部落的男鼠a1, b1, c1. 女鼠为a2, b2, c2.

不同的JP方案为a1-b2, b1-c2, c1-a2 和 a1-c2, b1-a2, c1-b2.

共两种方案

Limitation

$1 \le n \le 10^6$