#include<iostream>
using namespace std;
typedef long long LL;
struct mat{
int m[2][2];
};
mat mul(mat a,mat b){
mat ans;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans.m[i][j]=0;
for(int k=0;k<2;k++){
ans.m[i][j]+=a.m[i][k]*b.m[k][j];
}
ans.m[i][j]%=10000;
}
}
return ans;
}
mat qp(mat a,LL b){
mat ans={
1,0,
0,1
};
mat tem=a;
while(b){
if(b&1)//无括号
ans=mul(ans,tem);
tem=mul(tem,tem);
b>>=1;
}
return ans;
}
int main(){
LL n;
mat a={
1,1,
1,0
};
while(cin>>n&&n!=-1){
mat tem=qp(a,n);
cout<<tem.m[0][1]<<endl;
}
}
投递美团等公司6个岗位
