# Matrix Decomposition | CodeChef

Can someone help me to find out the error??
Edit: April cook off 2020 problem

https://www.codechef.com/viewsolution/32065125

You are supposed to use modular exponentition and increase i+=2 and not i++…here is my solution
https://www.codechef.com/viewsolution/32088797

in power function i have used 2*i-1

Then it might because of not using modular exponentition where we return (ans +mod)%mod…may be this might help

I couldn’t find the error. Can u check ??

Hi.
I think the error lies in your power function. When I used some large numbers to test out your power function, then the values overflow. This is probably why you are getting the wrong answer verdict.
As implemented by @mri_999, you can use modular exponentiation to calculate the powers. When I compared your codes, then there are a few differences here and there and probably that is why you are getting the issue.
You can use another function for faster calculation of power:

``````long long fast_power(long long base, long long power) {
long long result = 1;
while(power > 0) {

if(power % 2 == 1) {
result = (result*base) % MOD;
}
base = (base * base) % MOD;
power = power / 2; //
}
return result;
}
``````

The complexity for the same will be O(log(power)).

As @harsh0911 noted, your `powe` function is wrong.

The result for the parameters `1000, 1000` is incorrect.
It is due to `res*(tem*tem)%MOD`. This doesn’t work the way you expect it to and it overflows.

First it computes `res*(tem*tem)` and then it mods.
As all the terms can be upto 10^9+6, this will overflow.

Replacing `res*(tem*tem)%MOD` with `res*((tem*tem)%MOD)` is accpeted

The `powe` function is actually modular exponentiation. @rupinderg00 just made a silly mistake.

Can someone tell the error please?
int t=in.nextInt();
while(t–>0){
int n=in.nextInt();
long a=in.nextLong();
if(n==0){
System.out.println(0);
break;
}
long p[]=new long[n];
long sum=a;
p[0]=a;long h=1;
for(int i=1;i<n;i++){
a=(long)(a*p[i-1]);
p[i]=(long)Math.pow((a),h+2);
sum=sum+p[i]%1000000007;
h+=2;
}
System.out.println(sum);
}
Not getting it???