403195: GYM101064 B Buffaloes

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 = (b₁, ..., b_N) be a line of buffaloes, where b_i 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 (i₁, ..., i_L) is a possible family of size L if 1 ≤ i₁ < ... < i_L ≤ N and b_i1 > b_i2 > ... > b_iL, 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.

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

Limits

• 1 ≤ N ≤ 60

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

1

1

2

2

3

5

4

14

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.