how to avoid recursion:

``cache=[]
_build_dp=_build_dp
def _build_dp(last, s, array, rest, x, n):
    for j in reverse(len(n):
        if len(rest)>n:
            return 0
        if n==2:
            if s!=x:
                return 1
            else:
                return 0  
    _count=0
    if (len(rest)==n):
        for i in rest:
            if i!=s:
                _count+=_build_dp(s, i,  array, [ j for j in rest if j!=i ], x, n-1)
    else:
        for i in array:
            if i!=s:
                _count+=_build_dp(s, i,  array, [ j for j in rest if j!=i ], x, n-1)
        return _count

how to avoid recusrion?

!/bin/python3

import math import os import random import re import sys

#

Complete the 'countArray' function below.

#

The function is expected to return a LONG_INTEGER.

The function accepts following parameters:

1. INTEGER n

2. INTEGER k

3. INTEGER x

#

def _build_dp(last, s, array, rest, x, n): if len(rest)>n: return 0 if n==2: if s!=x: return 1 else: return 0
_count=0 if (len(rest)==n): for i in rest: if i!=s: _count+=_build_dp(s, i, array, [ j for j in rest if j!=i ], x, n-1) else: for i in array: if i!=s: _count+=_build_dp(s, i, array, [ j for j in rest if j!=i ], x, n-1) return _count

def countArray(n, k, x): _count=0 for i in range(2, k+1): _count+=_build_dp(1, i, range(1, k+1), [ i for i in range(2, k+1) if i!=x], x, n-1) return _count

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

k = int(first_multiple_input[1])

x = int(first_multiple_input[2])

answer = countArray(n, k, x)

fptr.write(str(answer) + '\n')

fptr.close()

public static long countArray(int n, int k, int x) { long mode = 1000000000 + 7; long[][] dp = new long[n + 1][2]; if (n == 2) { if (x == 1) return 0; else return 1; } if (x != 1) { dp[2][0] = 1; dp[2][1] = k - 2; } else { dp[2][0] = 0; dp[2][1] = k - 1; } for (int i = 3; i <= n; i++) { dp[i][0] = dp[i - 1][1] % mode; dp[i][1] = (dp[i - 1][1] * (k - 2) + dp[i - 1][0] * (k - 1)) % mode; }

    return dp[n][0];
}

I don't know where this code is wrong. I modularized it, but the answer is different.

static long mod(long x){
    while(x<0)
        x+=1000000007;
    return (x%1000000007);    
}
public static long countArray(int n, int k, int x)
{
// Return the number of ways to fill in the array.
    if(k<=1 || n<2)return 0;
    if(k==2 && n<=3) return 0;
    if(k==2)
    {
        if(x==1 ) 
        {
            if( n%2==0)  return 0;
            return 1;
        }
        if(x==2)
        {
            if( n%2==1)  return 0;
            return 1;
        }
    }

    long result= 1;
    int N=n-2;

    for(int i=0;i<N;i++)
    {
        result = mod(result*(k-1));
    }
    //result=mod(result*k);
    Console.WriteLine("result : "+result);
    long kn=1;
    for(int i=0;i<N-1;i++)
    {
        kn = mod(kn*(k-1));
    }
    Console.WriteLine("kn : "+kn);
    //result=mod(result-2*kn);
    Console.WriteLine("result : "+result);
    long ss1=0;
    long ss2=0;

        ss1 =mod(((kn+(k-1)*(((N-1)%2==0)?1:-1))/k));
        ss2 =mod(((kn+(((N)%2==0)?1:-1))/k));
    if(x==1)
    {
        kn=mod(ss2*(k-1));
    Console.WriteLine("ss1 : "+kn);
    }
    else 
    {
        kn=mod(ss2*(k-2)+ss1);
    Console.WriteLine("ss2 : "+kn);
    }
    return mod(result -kn);
}