Problem: A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits. For example, numbers 35270, 102, 747, 20 and 3 are wavy and numbers 123, 1000 and 2212 are not.

The task is to find the k-th smallest wavy number r that is divisible by n for the given integer values n and k.

You are to write a program that will find the value of r if it doesn't exceed 1014.

Input

The only line of input contains two integers n and k, separated by a single space (1 ≤ n, k ≤ 1014). 

Output

Your task is to output the only integer r — the answer to the given problem. If such number does not exist or it is larger than 1014, then print "-1" (minus one without the quotes) instead.

Examples

Input

123 4


Output

1845


Input

100 1


Output

-1


Input

97461 457


Output

1805270103

Note

The values of the first four wavy numbers that are divisible by n for the first sample are: 492, 615, 738 and 1845.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
const int MAXN = 100010;
const int INF = 1e9;
const long long PW = 10000000LL;
const long long PW2 = 1000000LL;
long long Pw;
int T;
int s[2][11][1000010];
long long N, K;
inline void dfs1(int d, int k, int x, int last, long long nw, int fr, int frt) {
  if (k == 8) {
    s[d][fr][(nw - frt + N) % N]++;
    return;
  }
  for (int i = 0; i < 10; i++)
    if ((k == 1 || ((last < i) ^ x)) && i != last)
      dfs1(d, k + 1, (k == 1 ? x : (last < i)), i, nw * 10 + i,
           (k == 1 ? i : fr), (k == 1 ? i : frt * 10));
  return;
}
long long D = 0;
inline void dfs4(int k, int x, int last, long long nw, long long lft) {
  if (k == 8) {
    if (nw % N == lft) {
      --K;
      if (!K) {
        printf("%lld\n", D * PW + nw);
        exit(0);
      }
    }
    return;
  }
  for (int i = 0; i < 10; i++)
    if (((last < i) ^ x) && i != last)
      dfs4(k + 1, (last < i), i, nw * 10 + i, lft);
}
inline void Find(int l, int r, int last, long long lft) {
  long long t = lft;
  lft = (lft - l * Pw % N + N) % N;
  for (int i = l; i < r; i++) {
    if (i != last) {
      if (lft < PW2) {
        if (K <= s[last < i][i][lft]) dfs4(2, (last < i), i, i, t);
        K -= s[last < i][i][lft];
      }
    }
    lft = lft - Pw;
    if (lft < 0) lft += N;
  }
  return;
}
inline void dfs2(int k, int x, int last, long long nw, int fr, int frt) {
  if (k == 8) {
    D = nw;
    if (!nw) return;
    long long lft = nw * PW % N;
    lft = (lft ? N - lft : 0);
    if (lft >= PW) return;
    if (nw < 10) {
      Find(0, 10, last, lft);
    } else if (x) {
      Find(0, last, last, lft);
    } else {
      Find(last + 1, 10, last, lft);
    }
    return;
  }
  if (!nw) last = -1;
  for (int i = 0; i < 10; i++)
    if ((k <= 2 || nw < 10 || ((last < i) ^ x)) && i != last)
      dfs2(k + 1, (k == 1 ? 2 : (last < i)), i, nw * 10 + i, (k == 1 ? i : fr),
           (k == 1 ? i : frt * 10));
  return;
}
inline void dfs3(int k, int x, int last, long long nw) {
  if (k == T) {
    if (nw % N == 0) --K;
    if (!K) {
      printf("%lld\n", nw);
      exit(0);
    }
    return;
  }
  if (!nw) last = -1;
  for (int i = (k == 1 ? 1 : 0); i < 10; i++)
    if ((k <= 2 || nw < 10 || ((last < i) ^ x)) && i != last)
      dfs3(k + 1, (k == 1 ? 2 : (last < i)), i, nw * 10 + i);
  return;
}
int main() {
  N = read(), K = read();
  Pw = (PW / 10) % N;
  dfs1(0, 1, 0, -1, 0, 0, 0);
  dfs1(1, 1, 1, -1, 0, 0, 0);
  for (int i = 2; i <= 8; i++) {
    T = i;
    dfs3(1, 2, -1, 0);
  }
  dfs2(1, 2, -1, 0, 0, 0);
  puts("-1");
  return 0;
}