给定一段有 阶的楼梯，你每一步可以选择上 阶或者 阶。求从楼梯底端走到顶端共有多少种不同的走法。由于答案可能很大，请将结果对 取模后输出。

输入描述:

在一行上输入一个整数 ，表示楼梯的阶数。

输出描述:

输出一个整数，表示不同走法的数量，对 取模后的结果。

备注:

提示，取模运算对加法运算满足交换律和结合律，所以在计算过程中多次取模得到的计算结果，和全部计算都完成后得到的计算结果是相同的。