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.


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).


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


Example Output


hide comments
dhruv2212000: 2019-02-17 14:17:44

Awesome Question :)

joydip007x: 2018-09-23 20:26:46

How can i understand that is it a bi-partitite 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 :)
and is there any other way to solve it ? like with permutation and combination , not graph theory ??

Last edit: 2018-09-23 20:28:04
mghazian: 2018-05-13 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: 2017-12-22 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: 2017-02-13 18:09:02

@Bhuvnesh Jain: here is case N==3. Hope it is view-able.

Also as you can see, my drawing skill are amazing so please do not sell this at auction! ©

Good Luck & Have Nice Day!

=(Francky)=> If need, you can include an image in the description of a problem. The better solution is to upload your image on spoj server. In the top banner, just below the comments, you have "upload files". Upload it with a name, and use it like the sample below in my problem REBOUND :
<p><img title="rebound" src="../../content/francky:rebound-fig2" alt="rebound" /></p>
It's always better to upload image on spoj server, for user in future. There are some problems with a missing image ; it was hosted elsewhere...

=(Morass)=> No - didn't want to include it in statement, since it is not a "nice image" but just some hand-drawing, to explain the test-case.

Anyway thank you so much for the explanation - I didn't know about this possibility and maybe I'll use it in the future ^_^

Secondly, seems the image is wrong and there shall not be connected two baby-carrots in the last example

Last edit: 2017-03-31 02:11:15
Bhuvnesh Jain: 2017-02-13 16:57:47

@author, can be please explain the test case with n = 3.

morass: 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!

abdou_93: 2017-02-13 10:20:09

@author i can't understand the description of the problem.
can you provide explanation for some test cases?

morass: 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

[Rampage] Blue.Mary: 2017-02-12 05:28:44

What's "N" in the input description? It is not specified in problem statement.

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