There are N balls placed in a row. AtCoDeer the deer is painting each of these in one of the K colors of his paint cans. For aesthetic reasons, any two adjacent balls must be painted in different colors.

Find the number of the possible ways to paint the balls.

Constraints

* 1≦N≦1000
* 2≦K≦1000
* The correct answer is at most 2^{31}-1.

Input

The input is given from Standard Input in the following format:


N K


Output

Print the number of the possible ways to paint the balls.

Examples

Input

2 2


Output

2


Input

1 10


Output

10
#include <bits/stdc++.h>
using namespace std;
bool judge(vector<int> jud_box) {
  if (jud_box.size() == 1) return true;
  for (int jud = 0; jud < jud_box.size(); jud++) {
    if (jud == 0) {
      if (jud_box[jud] == jud_box[jud + 1]) return false;
    } else if (jud == jud_box.size() - 1) {
      if (jud_box[jud - 1] == jud_box[jud]) return false;
    } else {
      if ((jud_box[jud] == jud_box[jud + 1]) or
          (jud_box[jud - 1] == jud_box[jud]))
        return false;
    }
  }
  return true;
}
int main(void) {
  int N, K;
  cin >> N >> K;
  int ans = 0;
  vector<int> box(N);
  int count = 0;
  int cycle_num = pow(N, K);
  for (int n = 0; n < cycle_num; n++) {
    int decimal = count;
    int binary = 0;
    int base = 1;
    while (decimal > 0) {
      binary += (decimal % K) * base;
      decimal /= K;
      base *= 10;
    }
    int digit = 0;
    int dig;
    while (binary) {
      dig = binary % 10;
      box[N - digit - 1] = dig;
      digit++;
      binary /= 10;
    }
    if (digit < N) {
      for (int j = 0; j < N - box.size(); j++) {
        box[j] = 0;
      }
    }
    if (judge(box)) ans++;
    count++;
  }
  cout << ans << endl;
}
