Description

我们知道斐波那契数列0 1 1 2 3 5 8 13……
数列中的第i位为第i-1位和第i-2位的和（规定第0位为0，第一位为1）。
求斐波那契数列中的第n位mod 10000的值。

Format

Input

多组数据，每组数据一个n（0<=n<=1 000 000 000）。
读入以-1结束。

Output

输出 Fn mod 10 000,若Fn的末4位都为0，则输出0；否则不要输出前导0。

Sample 1

Input

0
9
999999999
1000000000
-1

Output

0
34
626
6875

Limitation

1s, 64MiB for each test case.

Source

poj3070