Why this code is giving WA ? This question is based on Nth staircase (no. of ways to reach nth stair) Refer this Contest Page | CodeChef

```
const int maxn = 100006;
const int mod= 1000000007;
vector<ll> arr(maxn, 0);
int solve(ll n){
if(n<=2) return n;
if(n==3) return 4;
if(arr[n]!=0) return arr[n];
arr[n]=(solve(n-1)+solve(n-2)+solve(n-3)) % mod;
return arr[n];
}
int main(){
//solve();
int t; cin>>t;
while(t--){
ll n; cin>>n;
cout<<solve(n)<<endl;
}
return 0;
}
```