Server Time:

User's AC Ratio in this contest

100.0% (30/30)

Submission's AC Ratio in this contest

45.5% (30/66)

Description

給定正整數 $n$
請問有多少種長度為 $n$ 的 01 字串不包含 1+0+1+0+0+1+0+1+ 格式的子字串
(其中 + 表示前一字元重複 $1$ 次以上)

例如 11011 符合格式,而 00110111001 則不符合
因為 00110111001 包含了 01101,該子字串為 0+1+0+1+ 格式

Input Format

給定正整數 $n$ ($1 \leq n \leq 10^9$)

Output Format

輸出共有幾種長度為 $n$ 的 01 字串不包含 1+0+1+0+0+1+0+1+ 格式的子字串

Sample Input 1

20

Sample Output 1

382

Sample Input 2

2

Sample Output 2

4

Hints

  • 01 字串表示所有字元皆為 01
  • 子字串為原字串取其中一段連續的字元所構成的字串

第二筆範例 00011011 皆符合格式

Problem Source

Subtasks

No. Testdata Range Score
1 0~6 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 100 65536 65536 1
1 100 65536 65536 1
2 100 65536 65536 1
3 100 65536 65536 1
4 100 65536 65536 1
5 100 65536 65536 1
6 100 65536 65536 1