题目：

n 个沙茶，被编号 1~n。排完队之后，每个沙茶希望，自己的相邻的两人只要无一个人的编号和自己的编号相差为 1（+1 或-1）就行；

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

输入格式

只有一行且为用空格隔开的一个正整数 N。

输出格式

一个非负整数，表示方案数对 7777777 取模。

样例

样例输入

4

样例输出

2

正解是$O(n^2)$的暴力，但是$oeis$上给出了一个神奇的递推柿子： $a_n= (n+1)*a_{n-1} - (n-2)*a_{n-2} - (n-5)*a_{n-3} + (n-3)*a_{n-4}$

问了问之前也提出过这个问题的学长，表示也很疑惑

求大腿证明