You are a young student of mathematics having just started their first-year studies. You have been fully immersing yourself in your work and study and so classes have been going well so far, but as you leave class late one evening your professor has something they want to discuss with you. They commend your efforts towards your studies, but they also remind you that sometimes one must find some other pursuits to occupy your mind as well. "After all," they say, "there's more to life than just math problems". You nod, agreeing to make an effort to take your mind off of math problems for a while. You then say goodbye and head home, looking forward to dinner.
On your way home, you cross paths your childhood friend, who has since inherited his father's goat farm. He starts to tell you about a small problem he's been having recently, and you'd be just the person to help.
You see, he keeps his goats in a large pasture, which he wants to surround with a fence to keep
them from wandering off. His father had already placed 2 posts in the field, but your friend is
planning on placing P more posts , then stringing wire between each one to form a convex polygon.
He can then sub-divide this contained pasture by stringing together some more wire between any two
unconnected posts. However no two wires may cross paths, as they will rub against each other and
wear out over time. Also since the goats do not get along with one another, an "optimal layout"
is one where the maximum possible amount of subdivisions has been created. Additionally the grass
underneath the pen isn't necessarily uniform either, and so all non-identical rotations and reflections
of "optimal layouts" are considered unique. For example:
Layouts A, B, and C depict unique optimal layouts for P=3.
Layout D is not valid because two wires are crossing.
Layout E is not optimal because more subdivisions could be created.
If your friend sets P more posts in addition to the 2 already in the field, how many different
"optimal layouts" would be possible?
Problem Statement
Input data gives the number of testcases T on the first line.
The following T lines will contain P, the quantity of additional posts the farmer will set
around his pasture.
Answer should contain T space-separated integers corresponding to the quantity of unique
"optimal layouts" possible with P+2 posts. Give all answers modulo 1000000007.
Example
input data:
2
1
10
answer:
1 16796
You tell your friend that you would be happy to help him some other time, but at the moment you are quite tired and hungry from the long day and need to catch the train. The two of you part ways as you continue down the road.
Once you arrive at the train station, it appears that the old train is suffering a small problem.
If there are more or equal quantity people on the Left side of the train than on the Right, then
everything is safe. However, if at any given moment there are more people on the Right side of the
train than the Left, it will tip over. And so prior to boarding all the passengers must separate
into two groups based on if their tickets apply to seats on the Left or Right side of the train
and be careful about the order in which they board. Luckily tickets are always sold in Left/Right
pairs, so it is ensured that there will be an equal number of passengers having Left "L" tickets
and Right "R" tickets.
For example, a boarding order of RLLR would be safe, but a boarding order of LRRL would tip
the train.
If there are N passengers with Left-side tickets, and N passengers with Right-side tickets,
how many valid boarding orders exist which will not cause the train to tip?
Problem Statement
Input data gives the number of testcases T on the first line.
The following T lines will contain N, the quantity of ticket pairs on the train (giving a
total of 2*N passengers for each testcase).
Answer should contain T space-separated integers corresponding to the quantity of boarding
orders which do not cause the train to tip (assuming passengers with tickets of the same side are
indistinguishable). Give all answers modulo 1000000007.
Example
input data:
3
1
10
100
answer:
1 16796 558488487
You pause for a moment, then decide to walk home instead.
You don't usually walk through this old historic section of the city, and along your way you pass a beautiful brick wall covered in climbing ivy plants. Stopping to appreciate the quaint view, you notice a few things about the plants:
- At the base of each plant is a root node.
- From each node sprouts either a single leaf, or two more branches each ending in their own nodes.
Looking at the different plants on the wall, you see there are some different possibilities for
branching patterns for plants with L leaves:
Four unique branching patterns.
Problem Statement
Input data gives the number of plants P on the first line.
The following P lines will contain L, the quantity of leaves on the plant.
Answer should contain P space-separated integers corresponding to the quantity of unique
branching patterns possible for plants with L leaves. Consider any patterns which are reflections
of other patterns to be unique. Give all answers modulo 1000000007.
Example
input data:
4
1
10
100
1000
answer:
1 16796 558488487 110961515
You run home as quickly as you can, slamming the door behind you.
Taking a deep breath, you remove your shoes and jacket then head to the kitchen. You quickly take
out some ingredients for your favorite meal, but you realize you've misplaced your recipe book.
Determined to make your meal, you recall that there are I unique ingredients, but the end product
is very sensitive to the order in which the ingredients are added to each other.
For example if there were ingredients A, B, C, and D, then you could potentially take a
big mixing bowl and mix in ingredients in various sequences, such as ABCD, ABDC, ACBD, etc.
However, you could also pre-mix some subset of ingredients in some additional mixing bowl before
adding it to the main mixing bowl. For example, first making two separate mixtures of AB and CD,
and then mixing those together to form ABCD would be considered a unique mixing process as the
ingredients and mixtures will interact with each other differently during each sub-process. How
many different unique processes are possible for a recipe with I unique ingredients?
Problem Statement
Input data gives the number of recipes R on the first line.
The following R lines will contain I, the quantity of unique ingredients in the recipe.
Answer should contain R space-separated integers corresponding to the quantity of unique
mixing processes possible for a recipe with I ingredients. Give all answers modulo 1000000007.
Example
input data:
5
1
10
100
1000
10000
answer:
1 16796 558488487 110961515 512319131
You sit down on the couch for a moment to steady yourself. After a long silence, you reach over to the phone to call your professor. You tell him that you've considered his advice and may need a small vacation.