Given a number n. You are required to find ( Fib(n) ^ Fib(n) ) % 10^9 + 7, where Fib(n) is the nth fibonacci number.
Examples :
Input : n = 4
Output : 27
4th fibonacci number is 3
[ fib(4) ^ fib(4) ] % 10^9 + 7 = ( 3 ^ 3 ) % 10^9 + 7 = 27Input : n = 3
Output : 4
3th fibonacci number is 2
[ fib(3) ^ fib(3) ] % 10^9 + 7 = ( 2 ^ 2 ) % 10^9 + 7 = 4
If n is large, fib(n) will be huge and fib(n) ^ fib(n) is not only difficult to calculate but its storage is impossible.
Approach:
( a ^ (p-1) ) % p = 1 where p is prime number (using Fermat Little Theorem).
( a ^ a ) % m can be written as ( ( a % m ) ^ a ) % m
It is also possible to write any number ‘a’ as a = k * ( m – 1 ) + r (Using Division Algorithm)
where ‘k’ is quotient and ‘r’ is remainder. We can say that r = a % (m-1)
So, Steps to reduce our calculation, lets suppose a = fib(n)
( a ^ a ) % m = ( ( a % m ) ^ a ) % m = ( ( a % m ) ^ ( k * ( m - 1 ) + r ) ) % m = ( ( ( a % m ) ^ ( m-1 ) ) ^ k * ( a % m ) ^ r ) % m = ( (1 ^ k) * ( a % m ) ^ r ) % m = ( ( a % m ) ^ r ) % m = ( ( a % m ) ^ (a % (m-1) ) % m
a % m and a % (m-1) are easy to calculate and easy to store.
and we can calculate ( x ^ y ) % m using this GFG article.
We can find nth fibonacci number in log(n) time using this GFG article.
Below is the implementation of above approach :
C++
#include <bits/stdc++.h>#define mod 1000000007using namespace std; // Iterative function to compute modular powerlong long modularexpo(long long x, long long y, long long p){ // Initialize result long long res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; x = (x * x) % p; } return res;}// Helper function that multiplies 2 matrices// F and M of size 2*2, and puts the// multiplication result back to F[][]void multiply(long long F[2][2], long long M[2][2], long long m){ long long x = ((F[0][0] * M[0][0]) % m + (F[0][1] * M[1][0]) % m) % m; long long y = ((F[0][0] * M[0][1]) % m + (F[0][1] * M[1][1]) % m) % m; long long z = ((F[1][0] * M[0][0]) % m + (F[1][1] * M[1][0]) % m) % m; long long w = ((F[1][0] * M[0][1]) % m + (F[1][1] * M[1][1]) % m) % m; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;}// Helper function that calculates F[][] raise to // the power n and puts the result in F[][] // Note that this function is designed only for fib() // and won't work as general power function void power(long long F[2][2], long long n, long long m){ if (n == 0 || n == 1) return; long long M[2][2] = { { 1, 1 }, { 1, 0 } }; power(F, n / 2, m); multiply(F, F, m); if (n % 2 != 0) multiply(F, M, m);}// Function that returns nth Fibonacci number long long fib(long long n, long long m){ long long F[2][2] = { { 1, 1 }, { 1, 0 } }; if (n == 0) return 0; power(F, n - 1, m); return F[0][0];}// Driver Codeint main(){ long long n = 4; long long base = fib(n, mod) % mod; long long expo = fib(n, mod - 1) % (mod - 1); long long result = modularexpo(base, expo, mod) % mod; cout << result << endl;} |
Java
class GFG {static int mod = 1000000007;// Iterative function to compute modular powerstatic long modularexpo(long x, long y, long p){ // Initialize result long res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now y = y >> 1; x = (x * x) % p; } return res;}// Helper function that multiplies 2 matrices// F and M of size 2*2, and puts the// multiplication result back to F[][]static void multiply(long F[][], long M[][], long m){ long x = ((F[0][0] * M[0][0]) % m + (F[0][1] * M[1][0]) % m) % m; long y = ((F[0][0] * M[0][1]) % m + (F[0][1] * M[1][1]) % m) % m; long z = ((F[1][0] * M[0][0]) % m + (F[1][1] * M[1][0]) % m) % m; long w = ((F[1][0] * M[0][1]) % m + (F[1][1] * M[1][1]) % m) % m; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;}// Helper function that calculates F[][] raise to // the power n and puts the result in F[][] // Note that this function is designed only for fib() // and won't work as general power function static void power(long F[][], long n, long m){ if (n == 0 || n == 1) return; long M[][] = { { 1, 1 }, { 1, 0 } }; power(F, n / 2, m); multiply(F, F, m); if (n % 2 != 0) multiply(F, M, m);}// Function that returns nth Fibonacci number static long fib(long n, long m){ long F[][] = { { 1, 1 }, { 1, 0 } }; if (n == 0) return 0; power(F, n - 1, m); return F[0][0];}// Driver Codepublic static void main(String[] args){ long n = 4; long base = fib(n, mod) % mod; long expo = fib(n, mod - 1) % (mod - 1); long result = modularexpo(base, expo, mod) % mod; System.out.println(result);}}// This code is contributed by PrinciRaj1992 |
Python3
mod = 1000000007;# Iterative function to compute modular powerdef modularexpo(x, y, p): # Initialize result res = 1; # Update x if it is more than or # equal to p x = x % p; while (y > 0): # If y is odd, multiply x with result if (y & 1): res = (res * x) % p; # y must be even now y = y >> 1; x = (x * x) % p; return res;# Helper function that multiplies 2 matrices# F and M of size 2*2, and puts the# multiplication result back to F[][]def multiply(F, M, m): x = ((F[0][0] * M[0][0]) % m + (F[0][1] * M[1][0]) % m) % m; y = ((F[0][0] * M[0][1]) % m + (F[0][1] * M[1][1]) % m) % m; z = ((F[1][0] * M[0][0]) % m + (F[1][1] * M[1][0]) % m) % m; w = ((F[1][0] * M[0][1]) % m + (F[1][1] * M[1][1]) % m) % m; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;# Helper function that calculates F[][] raise to # the power n and puts the result in F[][] # Note that this function is designed only for fib() # and won't work as general power function def power(F, n, m): if (n == 0 or n == 1): return; M = [[ 1, 1 ], [ 1, 0 ]]; power(F, n // 2, m); multiply(F, F, m); if (n % 2 != 0): multiply(F, M, m);# Function that returns nth Fibonacci number def fib(n, m): F = [[ 1, 1 ], [ 1, 0 ]]; if (n == 0): return 0; power(F, n - 1, m); return F[0][0];# Driver Codeif __name__ == '__main__': n = 4; base = fib(n, mod) % mod; expo = fib(n, mod - 1) % (mod - 1); result = modularexpo(base, expo, mod) % mod; print(result);# This code is contributed by 29AjayKumar |
C#
using System;class GFG {static int mod = 1000000007;// Iterative function to compute modular powerstatic long modularexpo(long x, long y, long p){ // Initialize result long res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now y = y >> 1; x = (x * x) % p; } return res;}// Helper function that multiplies 2 matrices// F and M of size 2*2, and puts the// multiplication result back to F[,]static void multiply(long [,]F, long [,]M, long m){ long x = ((F[0, 0] * M[0, 0]) % m + (F[0, 1] * M[1, 0]) % m) % m; long y = ((F[0, 0] * M[0, 1]) % m + (F[0, 1] * M[1, 1]) % m) % m; long z = ((F[1, 0] * M[0, 0]) % m + (F[1, 1] * M[1, 0]) % m) % m; long w = ((F[1, 0] * M[0, 1]) % m + (F[1, 1] * M[1, 1]) % m) % m; F[0, 0] = x; F[0, 1] = y; F[1, 0] = z; F[1, 1] = w;}// Helper function that calculates F[,] raise to // the power n and puts the result in F[,] // Note that this function is designed only for fib() // and won't work as general power function static void power(long [,]F, long n, long m){ if (n == 0 || n == 1) return; long [,]M = { { 1, 1 }, { 1, 0 } }; power(F, n / 2, m); multiply(F, F, m); if (n % 2 != 0) multiply(F, M, m);}// Function that returns nth Fibonacci number static long fib(long n, long m){ long [,]F = { { 1, 1 }, { 1, 0 } }; if (n == 0) return 0; power(F, n - 1, m); return F[0, 0];}// Driver Codepublic static void Main(String[] args){ long n = 4; long Base = fib(n, mod) % mod; long expo = fib(n, mod - 1) % (mod - 1); long result = modularexpo(Base, expo, mod) % mod; Console.WriteLine(result);}}// This code is contributed by Rajput-Ji |
Javascript
<script>let mod = 1000000007;// Iterative function to compute modular powerfunction modularexpo(x, y, p){ // Initialize result let res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now y = y >> 1; x = (x * x) % p; } return res;}// Helper function that multiplies 2 matrices// F and M of size 2*2, and puts the// multiplication result back to F[][]function multiply(F, M, m){ let x = ((F[0][0] * M[0][0]) % m + (F[0][1] * M[1][0]) % m) % m; let y = ((F[0][0] * M[0][1]) % m + (F[0][1] * M[1][1]) % m) % m; let z = ((F[1][0] * M[0][0]) % m + (F[1][1] * M[1][0]) % m) % m; let w = ((F[1][0] * M[0][1]) % m + (F[1][1] * M[1][1]) % m) % m; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;}// Helper function that calculates F[][] raise to // the power n and puts the result in F[][] // Note that this function is designed only for fib() // and won't work as general power function function power(F, n, m){ if (n == 0 || n == 1) return; let M = [ [ 1, 1 ], [ 1, 0 ] ]; power(F, Math.floor(n / 2), m); multiply(F, F, m); if (n % 2 != 0) multiply(F, M, m);}// Function that returns nth Fibonacci number function fib(n, m){ let F = [ [ 1, 1 ], [ 1, 0 ] ]; if (n == 0) return 0; power(F, n - 1, m); return F[0][0];}// Driver Codelet n = 4;let base = fib(n, mod) % mod;let expo = fib(n, mod - 1) % (mod - 1);let result = modularexpo(base, expo, mod) % mod;document.write(result);// This code is contributed by code_hunt</script> |
Output:
27
Time Complexity: log(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
