#P2233. [HNOI2002] 公交车路线

    ID: 1249 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp矩阵乘法各省省选2002湖南

[HNOI2002] 公交车路线

题目描述

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

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

输入格式

仅有一个正整数 nn,表示 tiger 从公交车站 A 到公交车站 E 共换了 nn 次车。

输出格式

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

6
8

提示

8 条路线分别是:

(A→B→C→D→C→D→E),(A→B→C→B→C→D→E),

(A→B→A→B→C→D→E),(A→H→A→B→C→D→E),

(A→H→G→F→G→F→E),(A→H→G→H→G→F→E),

(A→H→A→H→G→F→E),(A→B→A→H→G→F→E)。

数据范围

4n1074\le n\le10^7