No.140 Group Trip
タグ : / 解いたユーザー数 114
作問者 : 👑
kmjp
Problem Statement
\(N\) married couples, \((2\times N)\) people in total, have decided to go on a trip.
The \((2\times N)\) people will split into several groups, and each group will travel by a car belonging to one of its members.
Every couple owns a large car, and if a group has one car, the whole group can travel in it.
However, a couple lets their car be used only if both spouses are in the same group.
In other words, for each group to be able to travel by car, the group must contain at least one married couple.
Find the number of ways to divide the people into groups that satisfy this condition.
Since the answer can be very large, output the value modulo \(10^9+7\).
Input
\(N\)
\(1 \le N \le 555\)
Output
Output on one line the number of ways to divide the people into groups so that everyone can travel safely.
Note that the execution time of the intended solution on the largest case is 1.2 seconds in Python.
Sample
Sample 1
Input
2
Output
2
Let the 2 couples be A-a and B-b. (A and a are a couple, and B and b are a couple.)
- There is 1 way to travel in 1 group: { AaBb }
- There is 1 way to travel in 2 groups: { Aa, Bb }
A combination such as { Ab, aB } does not satisfy the condition, because neither group can use a car.
Sample 2
Input
3
Output
11
Let the 3 couples be A-a, B-b, and C-c.
- There is 1 way to travel in 1 group: { AaBbCc }
- There are 9 ways to travel in 2 groups, as follows:
- { AaBb, Cc }, { AaCc, Bb }, { Aa, BbCc }
- { AaC, Bbc }, { Aac, BbC }, { ABb, aCc }, { aBb, ACc }, { AaB, bCc }, { Aab, BCc }
- There is 1 way to travel in 3 groups: { Aa, Bb, Cc }
Sample 3
Input
123
Output
658991534
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。