Description

森林里住着一只叫栗栗的小松鼠，它有个雷打不动的习惯：每天去松树林捡松果，捡回来的数量严格遵循一个规律——

• 第 0 天：刚搬新家，一颗都没有，捡到 0 颗

• 第 1 天：开张啦，捡到 1 颗

• 从第 2 天起：它每天捡到的颗数，恰好是昨天和昨天的昨天捡到的颗数加在一起（它说这是"祖传秘方"） eg:第2天捡到的松果为0+1=1颗

树洞门口挂着一台老式机械计数器，专门显示栗栗当天捡到的松果数。可惜这计数器年纪太大，最多只能数到 1e9（即10^9），再多数一颗就会"咔哒"一声归零重数——也就是说，它显示的数字永远是实际颗数 mod 1e9+1。

栗栗想知道：第 n 天，计数器上会显示几？

Format

Input

一个整数n，0≤n≤10^6

Output

一个整数，表示第n天计数器上显示的数字

Samples

10

55

0

0

1000

989415042

Limitation

1s, 1024KiB for each test case.