5362 - 组合数学:错排问题

通过次数

52

提交次数

111

Time Limit : 1 秒
Memory Limit : 128 MB

输入1个整数n,表示有1到n个整数,从小到大排列好,若每个数和他们的位置不相同,则认为是错排列,比如n=3时,正常是123,但是231、312就是2个错排列,输入1个整数n,请你求出其错排列的数量

Input

1个整数N (N<=10000)

Output

1个整数

Examples

Input

3

Output

2

Hint

都采用int即可