// Szybka rekurencja modularna
// www.algorytm.org
// (c) 2007 by Rafal Swietlicki

public class SRM {


	private static int[] potega_macierzy_modulo(int n, int t[], int a, int b, int m)
	{
	        int p1,p2;
	        if(n>=1)
	        {
	                t = potega_macierzy_modulo(n/2, t, a, b, m);
	                p1=t[0]+t[3];
	                p2=t[2];
	                t[0]=t[0]*t[0]+t[1]*t[2];
	                t[2]*=p1;
	                t[3]=t[3]*t[3]+t[1]*p2;
	                t[1]*=p1;
	                if(n%2 != 0)
	                {
	                        p1=t[0];
	                        t[0]=t[2];
	                        t[2]=t[2]*b+p1*a;
	                        p1=t[1];
	                        t[1]=t[3];
	                        t[3]=t[3]*b+p1*a;
	                }
	                t[0]%=m;
	                t[1]%=m;
	                t[2]%=m;
	                t[3]%=m;
	        }
	        else
	        {
	                t[0]=1;
	                t[1]=0;
	                t[2]=0;
	                t[3]=1;
	        }
	        return t;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
        int t[] = new int[4];
        int n,a,b,x,y,m,res;

        //dla ciagu Fibonacciego
        a = 1;
        b = 1;
        x = 1;
        y = 1;

        m = 10; //modulo 10 bo bedziemy obliczac tylko ostatnia cyfre

        System.out.println("Podaj n");
        n = Console.readInt("");
        if (n==0) res = x;
        else if (n==1) res = y;
        else
        {
                t = potega_macierzy_modulo(n-2, t, a, b, m);
                res = (x*(a*t[0]+b*t[2])+y*(a*t[1]+b*t[3])) % m;
        }
        System.out.println("Ostatnia cyfra liczby Fibonacciego numer " + n + " to " + res); 
	}

}