J19 实践-4 公交车路线

题目描述

长沙城新建的环城公路上一共有 $8$ 个公交站，分别为 $A$、$B$、$C$、$D$、$E$、$F$、$G$、$H$。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站 $A$ 到公交站 $D$，你就至少需要换 $3$ 次车。

$\text{Tiger}$ 的方向感极其糟糕，我们知道从公交站 $A$ 到公交 $E$ 只需要换 $4$ 次车就可以到达，可是 $\text{Tiger}$ 却总共换了 $n$ 次车，注意 $\text{Tiger}$ 一旦到达公交站 $E$，他不会愚蠢到再去换车。现在希望你计算一下$\text{Tiger}$ 有多少种可能的乘车方案。

输入格式

仅有一个正整数 $n$，表示 $\text{Tiger}$ 从公交车站 $A$ 到公交车站 $E$ 共换了 $n$ 次车。

输出格式

输出一个正整数表示方案数，由于方案数很大，请输出方案数除以 $1000$ 后的余数。

样例输入

6

样例输出

8

样例分析

8 条路线分别是：

$(A \to B \to C \to D \to C \to D \to E)$，$(A \to B \to C \to B \to C \to D \to E)$，

$(A \to B \to A \to B \to C \to D \to E)$，$(A \to H \to A \to B \to C \to D \to E)$，

$(A \to H \to G \to F \to G \to F \to E)$，$(A \to H \to G \to H \to G \to F \to E)$，

$(A \to H \to A \to H \to G \to F \to E)$，$(A \to B \to A \to H \to G \to F \to E)$。

数据范围

对于 $100\%$ 的数据：$4 \le n \le 10^7$。