ADACAROT - Ada and Carrot

Ada the Ladybug is a great farmer. She has many places where she grows vegetables. She wants to grow two completely different kinds of vegetable: carrots and baby carrots. She wants to connect them by paths in such way, that she can get from any carrot (or baby carrot) to any other carrot (or baby carrot). She isn't amused by building itself, so she wants to make least number of paths, which is sufficient to make all carrots (and all baby carrots) connected. Due to regulations of Earwigean Union (EU), a carrot can't be connected to other carrot (and same is true for baby carrots) [so basically, she can connect only "baby carrots" to "carrots"]. Ada also wants to keep track of everything, so she will somehow distinguish between each carrot and between each baby carrot (and also between each place).

She is wondering in how many ways she can plant carrots (and baby carrots) and connect them by ways, so that it corresponds to EU regulations.

Input

The input contains up to 200 lines. Each line consists of single integer 2 ≤ N ≤ 2*105 , the number of places to which carrots/baby carrots shall be placed (note that she won't waste so she will fill all the places).

Output

For each line of input, print the number of ways, to plant carrots and baby carrots in such way, that it coresponds to EU regulations. Since this number might be pretty big, output it modulo 109+7 (1000000007)

Example Input

2
3
4
10
66666

Example Output

2
12
144
452744977
57191401

Added by:Morass
Date:2017-02-12
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-02-13 16:57:47 Bhuvnesh Jain
@author, can be please explain the test case with n = 3.
2017-02-13 14:36:38
@abdou_93: Oh so sorry! Well, simply: You have N places and you have to place there N distinguishable objects and two-colorize them. Then you have to connect them by N-1 edges so it will become connected - but an edge can connect only nodes of different colors - how many ways? :) +/- - hope I didn't forget something

Have nice day & Good Luck!
2017-02-13 10:20:09 abdou_93
@author i can't understand the description of the problem.
can you provide explanation for some test cases?
2017-02-12 13:30:30
@[Rampage] Blue.Mary: Oh sorry, gotta try to repair that -- number of places, to which the carrots will be placed
2017-02-12 05:28:44 [Rampage] Blue.Mary
What's "N" in the input description? It is not specified in problem statement.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.