#10623. 走楼梯

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

有n阶楼梯,你可以选择走1阶或2阶。 现在你在楼梯下,请问你有多少种走法恰好能够走完这n阶楼梯?

输入格式

输入整数n(1<=n<=10^5)

输出格式

输出走法总数(数值很大,输出结果对123456789的余数)

样例

样例输入1

3

样例输出1

3

数据范围与提示

1<=n<=10^5