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*10^{5} , 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 10^{9}+7 (1000000007)
Example Input
2 3 4 10 66666
Example Output
2 12 144 452744977 57191401
hide comments
sangmai:
20200531 15:43:32
When n=4 is it correct if the case baby=1 and carrots=3 is counted. Since you cannot form a graph connecting all nodes just like what the description says. (If you connect all nodes there will be two carrots connected to each other). 

nadstratosfer:
20200225 17:24:09
Purely combinatorial problem, but the underlying graph sets the rules on how to go about it. That being said, one is unlikely to find the generalization the desired algorithm needs alone. I've spent 2 hours breaking down the cases for n < 7 only to have the internet tell me that the answer is the question I've begun my analysis with. 

rambo97:
20191003 09:49:46
How many time do we have to take input. It is not specified in the question


dhruv2212000:
20190217 14:17:44
Awesome Question :) 

joydip007x:
20180923 20:26:46
How can i understand that is it a bipartitite graph related problem. It was quite impossible for me until i saw the solution . .DOnt get my question wrong , i am newbie with graph theory :)


mghazian:
20180513 10:17:16
@nitangle With 1 carrot and 3 baby carrots, there are 24 configurations. With 2 carrots and 2 baby carrots there are 96 configurations. With 3 carrots and 1 baby carrot, there are 24 configurations. CMIIW 

nitangle:
20171222 20:29:11
Can someone please provide an explanation for N=4 case as well? I am not able to figure out how there will 144 ways. I can only get 96. 

morass:
20170213 18:09:02
@Bhuvnesh Jain: http://i.imgur.com/pcpZK3v.jpg here is case N==3. Hope it is viewable.


Bhuvnesh Jain:
20170213 16:57:47
@author, can be please explain the test case with n = 3. 

morass:
20170213 14:36:38
@abdou_93: Oh so sorry! Well, simply: You have N places and you have to place there N distinguishable objects and twocolorize them. Then you have to connect them by N1 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

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