【问题描述】 众所周知，美国企图利用帝国老鼠到中国传染病毒…他的病毒老鼠繁殖能力很强，而中国对此早有防备，但处于社会主义发展中国家的我们并没有能力去彻底把病毒消灭，只能从抑制老鼠的繁殖入手，现对这种成年每个月可以繁殖一对的老鼠进行繁殖抑制，使出生的一对小老鼠要在m个月后才能繁殖，现在需要正在为NOIP省一等奖奋斗的你，对n个月后老鼠的对数进行评估？ (假设小老鼠的生命力顽强，且初始第0个月只有1对成年老鼠。)（1 <= m <= 100,1<= n <= 107）

【输入】 只有一行：m和n

【输出】 对123456789取模后的结果

【样例】 输入：2 5 输出：13

样例解释 第0个月 1 第1个月 2 第2个月 3 第3个月 5 第4个月 8 第5个月 13