SPOJ.com - Problem ADACAROT

ADACAROT - Ada and Carrot

#number-theory

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⁵ , 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⁹+7 (1000000007)

Example Input

Example Output

Submit solution!

hide comments

< Previous 1 2 Next >

	Shrish Lal Bhatnagar: 2022-02-22 11:39:29 Although it is very beautiful question, description can be made better: 1. There are two types of vegetables B & C 2. You need to distribute these distinguishable vegetables across a field positions say 1 to n 3. After distributing the vegetables, you need to create path such that all nodes (vegetables) in this system are connected. 4. The number of edges in this path should be minimal (3 and 4 imply Spamming Tree of this graph) 5. All edges in this path should be B to C only (no B to B edges or C to C edges are allowed). 6. You need to find all such distributions, path combinations Hope this helps :), good luck Last edit: 2022-02-22 11:40:10
	tropo_sphere: 2020-12-01 15:19:26 when n=4, carrot=1 & baby carrot=3 =>4! carrot=2 baby carrot=2=> 4!(8) carrot=3 baby carrot=1 4! So, it comes 240 for me instead 144 Can anybodt explain? [NG]: 1-a-2-b is the same graph as b-2-a-1. Last edit: 2020-12-01 20:40:44*
	sangmai: 2020-05-31 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: 2020-02-25 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: 2019-10-03 09:49:46 How many time do we have to take input. It is not specified in the question
	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: http://i.imgur.com/pcpZK3v.jpg 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

Submit solution!

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