# WA in MATBREAK (Matrix Decomposition)

MATBREAK

``````#include <bits/stdc++.h>
#include <cmath>

using namespace std;

const long long mod = 1000000007;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, a;
cin >> n >> a;
long long temp = 1, power = 1;
vector <long long> pows(n);
pows[0] = 1;
for (int i = 1; i < n; ++i)
{
pows[i] = (temp+power)*((2*(i))+1);
temp += power;
power = pows[i];
}
unsigned long long s = 0;
for (int i = 0; i < n; ++i)
{
s += pow(a, pows[i]);
}
cout << (s % mod) << '\n';
}
}
``````

This works fine for the sample test cases. It gives a WA verdict though. How do I fix this?

You canâ€™t use pow for exponentiation. Search up modular exponentiation.

1 Like

I tried that too, but I got WA.

Just because you get wrong answer with modular exponentiation also, Doesnâ€™t mean you can use pow.

``````#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const ll p =1e9 + 7;
long long int modpower(ll b,ll po, ll mod=p){
long long int ans=1;
while(po){
if(po&1){
ans*=b;
ans%=mod;
}
b*=b;
b%=mod;
po>>=1;
}
return ans;
}
ll solve(){
ll n, a;
cin>>n>>a;
ll ans=0;
for(int i=1;i<=n;i++){
ans+=modpower(a, 2*i - 1);
ans%=p;
a*=modpower(a, 2*i -1);
a%=p;
}
cout<<ans<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
solve();
}
}
``````

Thatâ€™s literally all you need to do.

Thanks, I understood. Can you please explain the use of bitwise operators in `modpower()`?