First term from given Nth term of the equation F ( N ) = ( 2 * F ( N | C ++ program to implement the above approach ; Function to find the value of power ( X , N ) % M ; Stores the value of ( X ^ N ) % M ; Calculate the value of power ( x , N ) % M ; If N is odd ; Update res ; Update x ; Update N ; Function to find modulo multiplicative inverse of X under modulo M ; Function to find the value of F ( 1 ) ; Stores power ( 2 , N - 1 ) ; Stores modulo multiplicative inverse of P_2 under modulo M ; Stores the value of F ( 1 ) ; Update res ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  1000000007 NEW_LINE long long power ( long long x , long long N ) { long long res = 1 ; while ( N > 0 ) { if ( N & 1 ) { res = ( res * x ) % M ; } x = ( x * x ) % M ; N = N >> 1 ; } return res ; } long long moduloInverse ( long long X ) { return power ( X , M - 2 ) ; } long long F_1 ( long long N , long long F_N ) { long long P_2 = power ( 2 , N - 1 ) ; long long modInv = moduloInverse ( P_2 ) ; long long res ; res = ( ( modInv % M ) * ( F_N % M ) ) % M ; return res ; } int main ( ) { long long N = 3 ; long long F_N = 6 ; cout << F_1 ( N , F_N ) ; }