403195: GYM101064 B Buffaloes

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Buffaloestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

All teams participating on ICPC World Finals 2017, in Rapid City, were invited to make a visit to Custer State Park and relax a bit before the contest. Custer State Park is home to abundant wildlife, including bighorn sheep, antelope, deer, elk, coyote, and many other animals, including buffaloes.

As you know, buffaloes like to walk in a line. Many families of buffaloes walk in the same line, but they are not always in adjacent positions. However, buffaloes of the same family always stay in the same relative order in the line; an older buffalo always stays in front of a younger buffalo of his family, to protect him in case of any danger. Notice that, since there can be many different families in the line, the line isn't necessarily ordered by age.

Let b = (b1, ..., bN) be a line of buffaloes, where bi is the age of the ith buffalo. You can assume no two buffaloes in a line have the same age. We say a sequence of indexes (i1, ..., iL) is a possible family of size L if 1 ≤ i1 < ... < iL ≤ N and bi1 > bi2 > ... > biL, that is, it is not impossible that the buffaloes with these indices are in the same family. The family size of a line is the size of the largest possible family in that line.

As you and your team is taking a tour through the park, you sight a line of N buffaloes, and the instructor that is escorting you proposes the following puzzle: "In how many ways can you reorder the buffaloes in the line such that the family size of the line is not 3 or 4?".

Stefano "the swimmer" Spinnato, your coach, tells you "I can't distinguish the easy problems from the hard ones" and writes the solution in a piece of paper. You feel challenged and want to solve the puzzle too.

Input

A single integer N, the number of buffaloes in the line.

Limits

  • 1 ≤ N ≤ 60
Output

Print one integer, the answer to the problem. Since this number can be very large, print it modulo 109 + 7.

ExamplesInput
1
Output
1
Input
2
Output
2
Input
3
Output
5
Input
4
Output
14
Note

In the third case, assuming the 3 buffaloes age 1, 2 and 3, the possible lines are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) and (3, 2, 1). Of those, only line (3, 2, 1) has family size 3, so the answer is 5.

Source/Category

加入题单

上一题 下一题 算法标签: