static int mod=1000000007;
    // Complete the countArray function below.
    static long countArray(int n, int k, int x) {
        // Return the number of ways to fill in the array.
          if(n==3)
          {
              if(x==1)
              {
                  return 2;
              }
              else
              return 3;
          }
          long[][]dp=new long[n-2][2];

          for(int i=dp.length-1;i>=0;i--)
          {
              if(i==0)
              {
                   dp[i][0]=0;
        dp[i][1]=(
            (((k-1)*(dp[i+1][0]%mod))%mod)%mod +
                       (((dp[i+1][1]%mod)*(k-2))%mod)%mod     )%mod;
              }
              else if(i==dp.length-1)
              {
                  if(x!=1)
                  {
                      dp[i][0]=1;
                      dp[i][1]=(k-2);
                  }
                  else
                  {
                      dp[i][0]=0;
                      dp[i][1]=(k-1);
                  }
              }
              else
              {
                   dp[i][0]=dp[i+1][1]%mod;
        dp[i][1]=(
            (((k-1)*(dp[i+1][0]%mod))%mod)%mod +
                       (((dp[i+1][1]%mod)*(k-2))%mod)%mod     )%mod;
              }
          }
          return dp[0][1]%mod;
    }