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

题目描述

小红来到了一个  级台阶前。已知小红的左脚每次可以迈奇数级台阶，右脚每次可以迈偶数级台阶（不能是 0 ）
她准备用左、右脚交替的方式进行跳台阶：即除了第一步可以随意选择以外，后面的每一步的奇偶性一定和前一步不同。
小红想知道，自己跳上这  阶台阶，共有多少种不同的方式？答案对  取模

输入描述:

一个正整数 。  

输出描述:

小红上  级台阶的方案数对  取模的值。
示例1

输入

复制 
3

输出

复制 
3

说明

共有 3 种方案：
①先迈左脚，跳 1 级。然后迈右脚，跳 2 级
②先迈右脚，跳 2 级。然后迈左脚，跳 1 级
③直接迈左脚，跳 3 级。
示例2

输入

复制 
4

输出

复制 
2

说明

共有 2 种方案：
①先迈左脚，跳 1 级。然后迈右脚，跳 2 级，最后迈左脚，跳 1 级。
②直接迈右脚，跳 4 级。