【华为机试真题 JAVA】猴子爬山-100

【编程题目 |100分】猴子爬山【2021 H1,H2,2022 Q1 考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试“按钮进行代码提交。

题目描述

一天一只顽猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：
每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？

输入描述

输入只有一个整数N（0

输出描述

输出有多少种跳跃方式（解决方案数）。

测试用例

示例1

输入

50
1

输出

122106097
1

示例2

输入

3
1

输出