Your goal is to find the number of ways to construct an array such that consecutive positions contain different values.

Specifically, we want to construct an array with elements such that each element between and , inclusive. We also want the first and last elements of the array to be and .

Given , and , find the number of ways to construct such an array. Since the answer may be large, only find it modulo .

For example, for , , , there are ways, as shown here:

Complete the function countArray which takes input n, k and x. Return the number of ways to construct the array such that consecutive elements are distinct.

## solution in java

```
import java.util.Scanner;
class Solution {
public static final long MOD = 1_000_000_007L;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int x = sc.nextInt();
System.out.println(countArray(n, k, x));
sc.close();
}
public static long countArray(int n, int k, int x) {
long firstCount = 0, secondCount = 1;
for (int i = 3; i <= n; i++) {
long temp = secondCount * (k - 1) % MOD;
secondCount = (firstCount + secondCount * (k - 2)) % MOD;
firstCount = temp;
}
return x == 1 ? firstCount : secondCount;
}
}
```