問題一覧 > 通常問題

No.140 Group Trip

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 114
作問者 : 👑 kmjp
お気に入りにしたユーザー ProblemId : 251 / 自分の提出
問題文最終更新日: 2026-06-26 20:17:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 81 (順位表) の他の問題:

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 }
This gives 2 ways in total.
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 }
This gives 11 ways in total.
Sample 3
Input
123
Output
658991534

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。