Description

\(n\) 个沙茶, 被编号 \(1 - n\). 排完队之后, 每个沙茶希望, 自己的相邻的两人只要无一个人的编号和自己的编号相差为 \(1 (\pm 1)\) 就行;

现在想知道, 存在多少方案满足沙茶们如此不苛刻的条件.

Input

只有一行且为用空格隔开的一个正整数 \(n\).

Output

一个非负整数, 表示方案数对 \(7777777\) 取模.

Sample Input

4

Sample Output

2

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 1000\)

Explanation

我们发现这个问题可以转化为一个类似分治的做法. 我们可以用有一点像数学归纳法的搞法来做这题.

对于 \(n = 1\), 一定可行.

对于 \(n = 2\), 没有任何方法使得成立.

对于 \(n = 3\), 同样没有任何方法符合题意.

对于 \(n = 4\), 有两种情况 2 4 1 3 和 3 1 4 2 均符合题意.

那么针对所有的 \(n \geq 5\), 必定可以转化为 \(n\) 插入 \(n - 1\) 对应的序列中的方案, 这样的方案的种类数取决于插入的特性. 若插入的位置旁边没有 \(n - 1\), 则可以分开两个数值 (假如相邻的话, 不然维持原样不变); 若有, 则这个方案是不可行的. 按照这样的方法讨论, 我们可以抵达这样的做法:

构造一个数组 \(dp[n][n][2]\), 其中 \(dp[i][j][k]\) 为长度为 \(i\),\(n - 1\) 在第 \(j\) 个位置,\(k\) 代表 \(n - 1\) 是否和 \(n - 2\) 相邻.

然后随便转移一下水过此题~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 1010;
const lli modr = 7777777;

inline void add(lli& a, lli b) {
    a = (a + b) % modr; }

int n;
lli dp[maxn][maxn][2];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Dynamic programming
    dp[1][0][0] = 1;
    rep(i, 2, n) rep(j, 0, i - 1) {
        dp[i][j][1] = dp[i-1][j][1];
        if (j > 0)
            add(dp[i][j][1], dp[i-1][j-1][0] * 2 + dp[i-1][j-1][1]);
        add(dp[i][j][0], dp[i-1][j+1][1] * j);
        add(dp[i][j][0], dp[i-1][j+1][0] * (j + 1));
        add(dp[i][j][0], dp[i-1][j][1] * (i - j - 1));
        add(dp[i][j][0], dp[i-1][j][0] * (i - j - 2));
    }
    // Results
    lli res = dp[n][0][0];
    printf("%lld\n", res);
    return 0;
}