Optimization of Index coloring problem with one color adjacent allowed

I came across this index coloring problem (not exactly a typical Graph m-coloring problem) which I tried to solve using backtracking but the solution only works properly for lower-valued test cases and fails for larger ones due to exponential time complexity.

How can I optimize it such that it doesn't run in exponential time. Is there a DP approach to solve this?

Problem statement:

You are given 3 variables: n, k, x

n -> Number of indices to be colored

k -> Number of colors available -> 1,2,3,...K

x -> Color ID which can be used to color two adjacent indices.

You have to color n indices placed on the x-axis with k colors such that no two adjacent indices have the same color. However, you are also given x which is a colorID which is an exception to the above rule such that it is allowed to have two adjacent nodes with color = colorID.

You have to find out total number of ways all indices can be colored while following the above rules.

Example. For, n = 3 k = 2 x = 1 : All possible solutions are: (1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,1,2)

Following is my solution.

public class ColoringIndices {
    public static void main(String[] args) {
        int n = 17;
        int k = 4;
        int x = 3;
        placeColors(n, k, x);
    }

    static int count = 0;

    private static void placeColors(int n, int k, int x) {
        int currpos = 0;
        int[] arr = new int[n];
        placeColorsUtil(n, k, x, currpos, arr);
        System.out.println(count % 1000000007);
        count = 0;
    }

    private static void placeColorsUtil(int n, int k, int x, int currpos, int[] arr) {
        if(currpos == n){
            int mod = 1000000007;
            count = count % mod;
            count++;
            return;
        }

        for (int colorId = 1; colorId <= k; colorId++) {
            if (isSafe(colorId, currpos, arr, x)) {
                arr[currpos] = colorId;
                placeColorsUtil(n, k, x, currpos + 1, arr);
            }
        }
    }

    private static boolean isSafe(int colorId, int currpos, int[] arr, int x) {
        if (currpos < arr.length && currpos > 0) {
            if (colorId != x && arr[currpos - 1] == colorId) {
                return false;
            }
        }
        return true;
    }
}

Yes, the DP is whether the last index colored was x. We get two recurrences

X(n) = number of valid sequences of length n ending in x
Y(n) = number of valid sequences of length n not ending in x

X(1) = 1
Y(1) = k-1

X(n+1) = X(n) + Y(n)
         |  |   \__/
          \/     continue sequence not ending in x with x
           continue sequence ending in x with another x

Y(n+1) = (k-1) X(n) + (k-2) Y(n)
         |        |   \________/
         |        |    continue sequence not ending in x in k-2 possible ways
          \______/     (excluding the last color (not x in this case) and x)
           continue sequence ending in x in k-1 possible ways (excl. x)

which can be evaluated in time O(n). The answer is X(n) + Y(n) (or 0 if n is zero).

For posterity, I'll try to get an analytic solution. Meh, the presence of k makes this unfun. In practice you'd just be evaluating the appropriate power of the matrix

( 1   1 )
(k-1 k-2)

anyway.