No.336 Kadomatsu Sequence Sequence
タグ : / 解いたユーザー数 56
作問者 :
nmnmnmnmnmnmnm
Problem Statement
A Kadomatsu sequence is defined as follows: when 3 integers are arranged as A, B, C from left to right,
all the values are distinct and the second largest integer among A, B, C is either A or C.
In this problem, when some number of integers are arranged in a horizontal row from left to right,
if any 3 consecutive integers taken from it form a Kadomatsu sequence, the row is called a Kadomatsu sequence sequence.
When all permutations of the positive integers from 1 to N are considered,
how many of them are Kadomatsu sequence sequences?
Give the answer modulo 1000000007.
Note: when N=1 or N=2, 3 integers cannot be taken, so the answer is 0.
Input
N
The positive integer N from the problem statement. $1\le N \le 2016$.
Output
Print the answer modulo 1000000007 on one line.
Do not forget the newline at the end.
Sample
Sample 1
Input
1
Output
0
When N=1, no Kadomatsu sequence can be formed, so the answer is 0.
The answer is also 0 when N=2.
Sample 2
Input
3
Output
4
When N is 3, the permutations are the following 6:
{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}.
Among these, the Kadomatsu sequence sequences are the following 4:
{1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}.
Sample 3
Input
4
Output
10
The Kadomatsu sequence sequences are the following
{1,3,2,4}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}, {2,4,1,3},
{3,1,4,2}, {3,2,4,1}, {3,4,1,2}, {4,1,3,2}, {4,2,3,1},
10 in total.
Sample 4
Input
2016
Output
254936125
This is the maximum case. Do not forget to take the result modulo 1000000007.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。