#include <bits/stdc++.h>
using namespace std;
int freq[16];
long long dp[20][20];
long long factorial(long long n) {
  long long ans = 1;
  for (int i = 2; i <= n; i++) ans *= i;
  return ans;
}
long long nck(long long n, long long k) {
  return factorial(n) / (factorial(k) * factorial(n - k));
}
long long calculate1(int d) {
  if (d == 0) return 1;
  for (int i = 15; i >= 0; i--) {
    for (int j = 1; j <= d; j++) {
      dp[i][j] = 0;
      for (int k = 0; k <= freq[i]; k++) {
        if (j > k) {
          if (i != 15) dp[i][j] += nck(j, k) * dp[i + 1][j - k];
        } else if (j == k) {
          dp[i][j] += 1;
        }
      }
    }
  }
  return dp[0][d];
}
long long calculate(int d, bool zeroToBeCounted) {
  if (zeroToBeCounted)
    return calculate1(d);
  else {
    long long sum1 = 0;
    for (int x = 1; x <= d; x++) {
      for (int i = 1; i < 16; i++) {
        if (freq[i] == 0) continue;
        freq[i]--;
        sum1 += calculate1(x - 1);
        freq[i]++;
      }
    }
    return sum1;
  }
}
char encode(int i) {
  if (i <= 9)
    return (char)(i + '0');
  else
    return (char)('a' + i - 10);
}
string removeLeadingZeros(string &x) {
  int i;
  for (i = 0; i < x.length(); i++) {
    if (x[i] != '0') break;
  }
  if (i == x.length())
    return "0";
  else
    return x.substr(i);
}
string generateNumber(long long k) {
  string ans = "";
  bool zeroToBeCounted = false;
  for (int i = 0; i < 9; i++) {
    long long prefixSum = 0;
    int j;
    for (j = 0; j < 16; j++) {
      if (freq[j] == 0) continue;
      if (j == 0 && !zeroToBeCounted) {
      } else {
        freq[j]--;
      }
      long long temp;
      if (j == 0)
        temp = calculate(9 - i - 1, zeroToBeCounted);
      else
        temp = calculate(9 - i - 1, true);
      if (j == 0 && !zeroToBeCounted) {
      } else
        freq[j]++;
      long long temp2 = prefixSum + temp;
      if (temp2 >= k) break;
      prefixSum = temp2;
    }
    k -= prefixSum;
    if (j == 0) {
      if (zeroToBeCounted) freq[j]--;
    } else {
      freq[j]--;
      zeroToBeCounted = true;
    }
    ans += encode(j);
  }
  return removeLeadingZeros(ans);
}
int main() {
  int k, t;
  cin >> k >> t;
  for (int i = 0; i < 16; i++) freq[i] = t;
  cout << generateNumber(k) << endl;
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

Igor likes hexadecimal notation and considers positive integer in the hexadecimal notation interesting if each digit and each letter in it appears no more than t times. For example, if t = 3, then integers 13a13322, aaa, abcdef0123456789 are interesting, but numbers aaaa, abababab and 1000000 are not interesting.

Your task is to find the k-th smallest interesting for Igor integer in the hexadecimal notation. The integer should not contain leading zeros.

Input

The first line contains the two integers k and t (1 ≤ k ≤ 2·109, 1 ≤ t ≤ 10) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer.

It can be shown that the answer always exists for such constraints.

Output

Print in the hexadecimal notation the only integer that is the k-th smallest interesting integer for Igor.

Examples

Input

17 1


Output

12


Input

1000000 2


Output

fca2c

Note

The first 20 interesting integers if t = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. So the answer for the first example equals 12.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int freq[16];
long long dp[20][20];
long long factorial(long long n) {
  long long ans = 1;
  for (int i = 2; i <= n; i++) ans *= i;
  return ans;
}
long long nck(long long n, long long k) {
  return factorial(n) / (factorial(k) * factorial(n - k));
}
long long calculate1(int d) {
  if (d == 0) return 1;
  for (int i = 15; i >= 0; i--) {
    for (int j = 1; j <= d; j++) {
      dp[i][j] = 0;
      for (int k = 0; k <= freq[i]; k++) {
        if (j > k) {
          if (i != 15) dp[i][j] += nck(j, k) * dp[i + 1][j - k];
        } else if (j == k) {
          dp[i][j] += 1;
        }
      }
    }
  }
  return dp[0][d];
}
long long calculate(int d, bool zeroToBeCounted) {
  if (zeroToBeCounted)
    return calculate1(d);
  else {
    long long sum1 = 0;
    for (int x = 1; x <= d; x++) {
      for (int i = 1; i < 16; i++) {
        if (freq[i] == 0) continue;
        freq[i]--;
        sum1 += calculate1(x - 1);
        freq[i]++;
      }
    }
    return sum1;
  }
}
char encode(int i) {
  if (i <= 9)
    return (char)(i + '0');
  else
    return (char)('a' + i - 10);
}
string removeLeadingZeros(string &x) {
  int i;
  for (i = 0; i < x.length(); i++) {
    if (x[i] != '0') break;
  }
  if (i == x.length())
    return "0";
  else
    return x.substr(i);
}
string generateNumber(long long k) {
  string ans = "";
  bool zeroToBeCounted = false;
  for (int i = 0; i < 9; i++) {
    long long prefixSum = 0;
    int j;
    for (j = 0; j < 16; j++) {
      if (freq[j] == 0) continue;
      if (j == 0 && !zeroToBeCounted) {
      } else {
        freq[j]--;
      }
      long long temp;
      if (j == 0)
        temp = calculate(9 - i - 1, zeroToBeCounted);
      else
        temp = calculate(9 - i - 1, true);
      if (j == 0 && !zeroToBeCounted) {
      } else
        freq[j]++;
      long long temp2 = prefixSum + temp;
      if (temp2 >= k) break;
      prefixSum = temp2;
    }
    k -= prefixSum;
    if (j == 0) {
      if (zeroToBeCounted) freq[j]--;
    } else {
      freq[j]--;
      zeroToBeCounted = true;
    }
    ans += encode(j);
  }
  return removeLeadingZeros(ans);
}
int main() {
  int k, t;
  cin >> k >> t;
  for (int i = 0; i < 16; i++) freq[i] = t;
  cout << generateNumber(k) << endl;
  return 0;
}

```