How to solve this problem using dp when n<=10^8

can any on explain???

Do you know about this concept? If you don’t go through this, you will get this question easily.

In case you don’t, I will write it’s program and send it here, as soon as possible.

Using dp it can be done as this, but it will not pass all test cases.

```
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t;
cin >> t;
while(t--)
{
ll n;
cin >> n;
ll dp[n+1];
dp[0] = 9;
dp[1] = 31;
for(int i=2;i<=n;i++)
{
dp[i] = ((8*dp[i-1])%mod - (15*dp[i-2])%mod + mod)%mod;
}
cout << dp[n] << "\n";
}
return 0;
}
```

yeah thanks i have tried by understanding of that topic but i got wrong

could you tell where i am wrong??

my solution link

Your submission is not visible.

you can try something like this

Can anyone explain what’s wrong here? Forget about internal tests cases, its printing 2nd example output more than 100 times.

```
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long int tests;
cin >> tests;
while(tests--){
unsigned long long int n;
cin >> n;
if(n==1) cout << 31 << "\n";
else {
unsigned long long int f[n];
long long int m=1000000007;
f[0]=9;
f[1]=31;
long long int k=2;
while(k<=n){
f[k]=8*f[k-1]%m-15*f[k-2]%m;
k++;
}
cout << f[n] << "\n";
}
}
return 0;
}
```

thank you i have figured it out by correcting (a-b)%m formula and it is accepted