get nth fibonacci c 2b 2b

1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long;
4const ll mod =1e9+7;
5unordered_map <ll,ll> f;
6
7ll fib(ll n) {
8	if(n < 2) return 1;
9	if (f.find(n) != f.end()) 
10		return f[n];
11	f[n] = (fib((n+1)/2)*fib(n/2) + fib((n-1)/2)*fib((n-2)/2)) % mod;
12	return f[n];
13}
14main() {
15	int t; cin >> t;
16	while ( t--) {
17		ll n;
18		cin >> n;
19		cout << fib(n-1) << "\n";
20	}
21}
22/*
23Input         Output
243           
252             1
266             8
2720            6765
28*/