最后的晚餐(dinner)
题号:NC19857
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

    **YZ(已被和谐)的食堂实在是太挤辣!所以Apojacsleam现在想邀请他的一些好友去校外吃一顿饭,并在某酒店包下了一桌饭。
    当Apojacsleam和他的同学们来到酒店之后,他才发现了这些同学们其实是N对cp,由于要保护广大单身狗的弱小心灵(FF!),所以他不想让任意一对情侣相邻。
    说明:
        ·酒店的桌子是恰好有2N个位置的圆桌。
        ·客人恰好是N对cp,也就是说,圆桌上没有空位。
        ·桌子的每一个位置是一样的,也就是说,如果两种方案可以通过旋转得到,那么这就可以视为相等的。
    现在,你需要求出,将任意一对情侣不相邻的方案数。
    ·

输入描述:

一行一个正整数N,表示cp的对数。

输出描述:

一行一个非负整数,表示答案对1000000007取模后的值。
示例1

输入

复制
2

输出

复制
2

说明

两种方案:

假设1-2、3-4是两对情侣。

方案有1-3-2-4

1-4-2-3

或者你也可以认为1-3-2-4

2-3-1-4

是合法的方案。
示例2

输入

复制
25

输出

复制
535659175
示例3

输入

复制
1000000

输出

复制
270258012

说明

对于20%的数据,1<=N<=5
对于30%的数据,1<=N<=20
对于50%的数据,1<=N<=100
对于70%的数据,1<=N<=200000
对于100%的数据,1<=N<=30000000