I have a problem about measuring the Time Complexity of the Problem

according to me, it should be O(n^3), n^2 due to dp and O(N) due to transitions , so in total O(N^3)

Constraints:

2≤N≤2000

1≤M≤2000

1≤K≤2000

int dp[2][2001][2001];

int fun( vector g[],int node,int dis,int cnt){

if( dis == k+1 ){
    if( cnt%2 || node != t ) return 0;
    return 1;
}

if( dp[cnt][node][dis] != -1 )return dp[cnt][node][dis];

int ans = 0;
for(auto child: g[node]){
    int n_cnt = cnt;
    if( child == x ) n_cnt^=1;
    ans = (ans%M+fun(g,child,dis+1,n_cnt)%M)%M;
}

return dp[cnt][node][dis]=ans;

}

It is Atcoder's King Bombee problem! Link: https://atcoder.jp/contests/abc244/tasks/abc244_e