I got no idea why am i getting wrong answer for this. Thanks in advance
include <bits/stdc++.h>
using namespace std;
define int long long
define fastread() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
int MOD = 1e9;
int binaryMul(int a,int b,int mod){
int ans = 0;
a=a%mod;
while(b){
if(b&1) ans = (ans + a)%mod;
a = (a+a)%mod;
b>>=1;
}
return ans;
}
int binaryExpo(int a,int b,int mod){
int ans = 1;
while(b){
if(b&1){
ans = binaryMul(ans,a,mod)%mod;
}
a = binaryMul(a,a,mod)%mod;
b>>=1;
}
return ans;
}
int inverse(int b,int mod){
return (binaryExpo(b,mod-2,mod)%mod);
}
signed main() {
fastread();
int n;
cin>>n;
vector arr(n,0);
for(auto &i:arr) cin>>i;
vector pre(n+1,1);
for(int i = 1;i<=n;i++){
pre[i]=binaryMul(pre[i-1],arr[i-1],MOD);
}
int q;
cin>>q;
while(q–){
int l,r,m;
cin>>l>>r>>m;
int ans = pre[r];
if(l>1)
ans = binaryMul(pre[r],inverse(pre[l-1],m),m);
cout<<ans<<endl;
}
return 0;
}