填数游戏

题号：NC214615
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

菜菜杰迷上了填数游戏，游戏规则是，在n个格子上依次填上数字0或者1，但在填上0后不能在其后面相邻的位置上填1。菜菜杰想知道总共有多少种方案。若两种方案至少有一个位置填色不同，即为不同方案。

仅一行，输入n (1<=n<=1000000)

输出方案数

示例1

复制

复制