public class Assignemnt1 {

    static long cntr=1;
    static long[][]a1={{1},{0}};
    static long[][]auxMat={{1,1},{1,0}};
    static long[][]b1 = new long[2][2];
    private static long startTime, endTime, elapsedTime;
    private static int phase = 0;
    public static long RecFib(long n,int p) // 2 raise to power n ::time complexity
    {
        long ans;
        if(n%p<2) return(n%p);
        else
        return RecFib((n-1)%p,p)+RecFib((n-2)%p,p);
}



     public static long FibDP(long fib)
     {
         long []a = {0,1};

         for (int i=2;i<=fib;i++)
         {
            Long ans =( a[0])+(a[1]);
            a[0]=a[1];
            a[1]=ans;

         }
         return(a[1]);

     }

     public static long RecFibMatrix(long fib,int p)// to get O(n)
        {

        if(fib<2) return fib;
        else
            calculatePower(fib,p);

        return (b1[0][0]);
        }

public static void calculatePower(long fib,int p)
    {

    while(cntr<fib)
    {
        multiplyMatrix(p);
        cntr++;

    }
    }

        public static long RecFibMatrixDAC(long fib,int p)// to get O(logn)
{

            if(fib<2) return fib;
            else
                calculatePower(fib,p);

            return ((b1[0][0]*a1[0][0])+(b1[1][0]*a1[1][0])%p);
}

    public static void calculatePowerDAC(long fib,int p)
    {

    while(cntr<(fib/2)+1)
    {
        multiplyMatrix(p);
        cntr++;

    }



    }


    public static void multiplyMatrix(int p)
    {
        b1[0][0]=(auxMat[0][0]*a1[0][0]+auxMat[0][1]*a1[1][0])%p;
        b1[1][0]=(auxMat[1][0]*a1[0][0]+auxMat[1][1]*a1[1][0])%p;

        a1[0][0]=b1[0][0];
        a1[1][0]=b1[1][0];


    }


    public static void timer()
    {
        if(phase == 0) {
        startTime = System.currentTimeMillis();
        phase = 1;
    } else {
        endTime = System.currentTimeMillis();
            elapsedTime = endTime-startTime;
            System.out.println("Time: " + elapsedTime + " msec.");
            //memory();
            phase = 0;
        }
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
     timer();
    long ans=RecFibMatrixDAC(1234567890,997);
    System.out.println(ans);
    timer();
    }

}