Matrix Decomposition problem in April Cook-Off 2020.
Cannot figure out why the solution below is giving W/A verdict. Algorithm used is similar to the editorial. Any clues and insights regarding the mistakes are really appriciated.
#include <stdio.h>
#define m 1000000007
using namespace std;
long long int modExp(long long int x,long long int y)
{
if(y==0)
return 1;
long long int temp=modExp(x,y/2);
if(y%2==0)
return (temp*temp)%m;
else
return (((temp*temp)%m)*x)%m;
}
int main()
{
int t,n,i;
long long int res,a,curr,pi;
scanf("%d",&t);
while(t)
{
scanf("%d %lld",&n,&a);
if(a==0)
printf("0\n");
else if(a==1)
printf("%d\n",n);
else
{
curr=a;
res=0;
for(i=1;i<=n;i++)
{
pi=modExp(curr,2*i-1);
res=(res+pi)%m;
curr=(curr*pi)%m;
}
printf("%lld\n",res);
}
t--;
}
return 0;
}