Description

我们知道斐波那契数列f0=0,f1=1,f(n)=f(n-1)+f(n-2) 。

求f(n) mod 10^4 。

Input Format

组数据，每组数据一行，一个整数 n。

输入以-1结束。

Output Format

于每组数据，输出 f(n) mod 10^4。

Sample

输入

0
9
999999999
1000000000
-1

输出

0
34
626
6875

Hint

对于全部数据，0=<n<=10^9。