Answers for "get nth fibonacci c++"

get nth fibonacci c++

#include <bits/stdc++.h>
using namespace std;
#define ll long long;
const ll mod =1e9+7;
unordered_map <ll,ll> f;

ll fib(ll n) {
	if(n < 2) return 1;
	if (f.find(n) != f.end()) 
		return f[n];
	f[n] = (fib((n+1)/2)*fib(n/2) + fib((n-1)/2)*fib((n-2)/2)) % mod;
	return f[n];
}
main() {
	int t; cin >> t;
	while ( t--) {
		ll n;
		cin >> n;
		cout << fib(n-1) << "\n";
	}
}
/*
Input         Output
3           
2             1
6             8
20            6765
*/