/**
 * @file 
 * @brief This program computes the N^th Fibonacci number in modulo mod
 * input argument .
 *
 * Takes O(logn) time to compute nth Fibonacci number
 * 
 *
 * \author [villayatali123](https://github.com/villayatali123)
 * \author [unknown author]()
 * @see fibonacci.cpp, fibonacci_fast.cpp, string_fibonacci.cpp, fibonacci_large.cpp
 */

#include<iostream>
#include<vector>
#include <cassert>

/**
 * This function finds nth fibonacci number in a given modulus
 * @param n nth fibonacci number
 * @param mod  modulo number 
 */
uint64_t fibo(uint64_t n , uint64_t mod )
{
	std::vector<uint64_t> result(2,0);
	std::vector<std::vector<uint64_t>> transition(2,std::vector<uint64_t>(2,0));
	std::vector<std::vector<uint64_t>> Identity(2,std::vector<uint64_t>(2,0));
	n--;
	result[0]=1, result[1]=1;
	Identity[0][0]=1; Identity[0][1]=0;
	Identity[1][0]=0; Identity[1][1]=1;
	 
	transition[0][0]=0;
	transition[1][0]=transition[1][1]=transition[0][1]=1;
	
	while(n)
	{
		if(n%2)
		{
			std::vector<std::vector<uint64_t>> res(2, std::vector<uint64_t>(2,0));
	                for(int i=0;i<2;i++)
			{
				for(int j=0;j<2;j++)
				{
					for(int k=0;k<2;k++)
						{
							res[i][j]=(res[i][j]%mod+((Identity[i][k]%mod*transition[k][j]%mod))%mod)%mod;
						}
				}
			}
		       	for(int i=0;i<2;i++)
			{
				for(int j=0;j<2;j++)
				{
				Identity[i][j]=res[i][j];
				}
	    		}
			n--;
		}
		else{
			std::vector<std::vector<uint64_t>> res1(2, std::vector<uint64_t>(2,0));
			for(int i=0;i<2;i++)
			{
				for(int j=0;j<2;j++)
				{
					for(int k=0;k<2;k++)
					{
						res1[i][j]=(res1[i][j]%mod+((transition[i][k]%mod*transition[k][j]%mod))%mod)%mod;
					}
				}
			}
			for(int i=0;i<2;i++)
			{
				for(int j=0;j<2;j++)
				{
					transition[i][j]=res1[i][j];
				}
			} 
			n=n/2;
			}
	}
	return ((result[0]%mod*Identity[0][0]%mod)%mod+(result[1]%mod*Identity[1][0]%mod)%mod)%mod;
}

/**
 * Function to test above algorithm
 */
void test()
{
    assert(fibo(6, 1000000007 ) == 8);
    std::cout << "test case:1 passed\n";
    assert(fibo(5, 1000000007  ) == 5);
    std::cout << "test case:2 passed\n";
    assert(fibo(10 , 1000000007) == 55);
    std::cout << "test case:3 passed\n";
    assert(fibo(500 , 100) == 25);
    std::cout << "test case:3 passed\n";
    assert(fibo(500 , 10000) == 4125);
    std::cout << "test case:3 passed\n";
    std::cout << "--All tests passed--\n";
}

/**
 * Main function
 */
int main()
{
	test();
	uint64_t mod=1000000007;
	std::cout<<"Enter the value of N: ";
	uint64_t n=0; std::cin>>n; 
	std::cout<<n<<"th Fibonacci number in modulo " << mod << ": "<< fibo( n , mod) << std::endl;
}