#1265. Sparky 与 Python

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sparky_14145

题目描述

题目背景

Sparky 喜欢翻转东西。这天,他看到了一条可爱的 Python,他发现这条 Python 的鳞片似乎可以被翻转,他决定尝试翻转一下。但是,他不能够惊动 Python,否则 Python 会咬他……

题目描述

Python 的鳞片被从头到尾依次编号为 1 \ldots n n 个单位区域,初始时每个单位区域的状态均为“正”。Sparky 每次可以选择一个状态为“正”的区域,并将它的状态变为“反”。

但是,在 Sparky 手贱完后,每一个状态为“反”的单位区域必须与至少一个状态为“反”的单位区域相邻,否则 Python 会感到不适并且咬 Sparky 一口。

比如这些结果是允许的(Sparky 不会被 Python 咬):

  • |正|正|正|正|
  • |反|反|反|
  • |反|反|正|反|反|

而以下结果不被允许(Sparky 会被 Python 咬):

  • |正|(反)|正|
  • |正|正|(反)|
  • |反|

现在,Sparky 希望知道有多少种可能的结果,能够使得自己不被咬。由于这个结果可能很大,你只需要输出它对 19260817 取模的结果。

输入格式

输入文件仅一行,包含一个整数 n ,表示 Python 被划分成的单位区域数。

输出格式

输出文件仅一行,包含一个整数,表示方案数对 19260817 取模的结果。

样例

样例输入输出 1:

样例输入 1:

3

样例输出 1:

4

样例输入输出 2:

样例输入 2:

6

样例输出 2:

21

样例输入输出 1 解释:

所有方案如下:

  • |正|正|正|
  • |正|反|反|
  • |反|反|反|
  • |反|反|正|

数据范围与提示

数据范围

对于 10\% 的数据, n \leq 6
对于 30\% 的数据, n \leq 20
对于 60\% 的数据, n \leq 10^6
对于 100\% 的数据, n \leq 10^{12}

提示

在任何时候,仅含 1 个“反”的方案均为不合法的。

对于大范围数据,请不要忘记取模。刚刚 Sparky 用 Python 造数据时忘记取模结果电脑死机了。

题目并不难!