integer::a(6**9)=0;a(1)=1;n=2e3;do i=1,6e6;k=a(i)*4+k/10;a(i+n)=mod(k,10);enddo;1 read*,k;print'(i0)',sum(a(k*n:k*n+n));goto1;end