My solution is as follows and works well according to me but I’m getting wrong answer when submitting it.
#include <iostream>
using namespace std;
#define ll long long
ll power(ll a, ll b, ll m = 1000000007){
int res = 1;
while(b>0){
if(b&1) res = (res*a)%m;
a = (a*a)%m;
b = b>>1;
}
return res;
}
ll breakinteger(ll n){
if(n==2) return 1;
if(n==3) return 2;
ll ans;
switch(n%3){
case 0:
ans = power(3, n/3);
break;
case 1:
ans = 4*power(3,(n/3)-1);
break;
case 2:
ans = 2*power(3,n/3);
break;
}
return ans;
}
int main() {
int t;
ll input;
cin >> t;
for(int i=0;i<t;i++){
cin>>input;
cout<<breakinteger(input)<<endl;
}
return 0;
}