NUM = 10**9+7

def countArray(n, k, x):
    dp = [[0 for _ in range(2)] for _ in range(n+1)]
    
    # dp[length][ends in x]
    
    dp[2][0] = k - 2 if x != 1 else k - 1
    dp[2][1] = 1 if x != 1 else 0
    
    for i in range(3, n+1):
        dp[i][0] = ((((k-2) % NUM) * (dp[i-1][0] % NUM)) % NUM + (((k-1) % NUM) * (dp[i-1][1] % NUM)) % NUM) % NUM
        dp[i][1] = dp[i-1][0] % NUM
    
    return dp[n][1] % NUM

My initial solution - which consumed too much memory - involved computing the number of arrays that could be constructed that concluded with a specific number l but, at its limit it creates a memoisation array of size 4 x 10¹⁰ bytes which is... a bit too much RAM usage. However, ultimately all that matters is whether or not it ended with x or not.

Cautious, the modulo requirement can make a Huge difference. You may not pass other tests than 0 & 1 unless "mod" is used in the correct place and with correct value, even if your solution is all correct.

This problem required very little memoization. I noticed a pattern; consider the number of arrays of length 2: [0,1,1] where index is the ending number x. Using a dynamic coding strategy, you might try to find the number of arrays of length 3 by summing up elements of this array: [2,1,1] You don't add the number of arrays of length 2 ending in the same x, since the numbers can't appear twice in a row. Therefore, index 1 is one greater, since it ignored the one element that was 1 less than the others. Using this array, the number of arrays of length 4 is: [2,3,3] This time, index 1 is one less since it ignored the one element that was one more than the rest. The pattern continues: [6,5,5] [10,11,11]

So we can ditch using arrays and just consider the number of arrays ending in x>1. The number N(n) of arrays of length n ending in x>1 is equal to (k-1)*N(n-1) + (1 if n is even, -1 if n is odd)

if x==1, subtract 1 if n is even, add 1 if n is odd

function countArray(n: number, k: number, x: number): number {
    // Return the number of ways to fill in the array.
    //ending in number col+1
    //array of length row+2
    //NOTE: for EVEN length, there is one less array ending in 1. for ODD, there is one extra.
    // Otherwise, the number of constructable arrays of length n ending in k is equal to the sum of all arrays of length n-1, + or - one depending on n's parity.
    let curr = 1;
    
    let mod = (Math.pow(10,9)+7)
    
    let even;
    let odd;
    //iterate over possible lengths
    for(let i=2; i<n; i++)
    {
        even = i%2
        odd = even==1?0:1
        //add even bonus, remove odd
        curr = (curr*(k-1) + even - odd) % mod
    }
    if(x==1) curr += (-even + odd)
    
    return curr
}

Did not understand why my code passed only first 2 testcases and failed all the rest until I realized that the modulo code was not in the right place.

If you comment your modulo code and it passes the testcases below when n<12 but will fail as soon as n=12 , then your code is very close to the solution.

10 10 2 38742049

11 10 2 348678440

12 10 2 138105940

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