Description

大家都知道 Fibonacci 数列F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for 求第n项 mod 10000的值。

Input Format

多组数据，每组数据一个n. 读入以-1结束。

Output Format

输出 fn mod 10000.若的末4位都为0，则输出0，否则不要输出前导0.

Sample

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

Hint

where 0 ≤ n ≤ 1,000,000,000