#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <typename X>
inline X abs(const X& a) {
  return a < 0 ? -a : a;
}
template <typename X>
inline X sqr(const X& a) {
  return a * a;
}
const int size = 1e5 + 2;
const double eps = 0.0001;
const long double PI = 3.1415926535897932384626433832795;
const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const long long MAX5 = 100001;
const long long MAX6 = 1000001;
const long long MAX17 = 99999999999999999;
const double DMAX = 2e18 + 5;
void solution();
void include_file();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solution();
  return 0;
}
void include_file() {
  ios_base::sync_with_stdio(true);
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
inline bool isPrime(long long n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return true;
}
string ekv(string a) {
  if (a.size() & 1) return a;
  string x = ekv(a.substr(0, a.size() / 2));
  string y = ekv(a.substr(a.size() / 2));
  return min(x + y, y + x);
}
long long cubic_root(long long x) {
  long long l = 0, r = MAX6;
  while (l != r) {
    long long m = (l + r + 1) / 2;
    if (m * m * m > x)
      r = m - 1;
    else
      l = m;
  }
  return l;
}
float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i >> 1);
  x = *(float*)&i;
  x = x * (1.5f - (xhalf * x * x));
  return x;
}
long long gcd(long long a, long long b) {
  while (b ^= a ^= b ^= a = a % b)
    ;
  return a;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
constexpr uint64_t mod = (1ull << 61) - 1;
uint64_t modmul(uint64_t a, uint64_t b) {
  uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
  uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  uint64_t ret =
      (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  ret = (ret & mod) + (ret >> 61);
  ret = (ret & mod) + (ret >> 61);
  return ret - 1;
}
void yes() { cout << "YES"; }
void no() { cout << "NO"; }
void yes(bool res, bool small = false) {
  if (!small) {
    if (res)
      cout << "YES";
    else
      cout << "NO";
  } else {
    if (res)
      cout << "Yes";
    else
      cout << "No";
  }
}
void dabl(double x) { printf("%.10lf", x); }
namespace bits {
template <typename X>
inline X MAX(const X& a, const X& b) {
  return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
}
template <typename X>
inline X MIN(const X& a, const X& b) {
  return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
}
bool check2(const long long n) { return n > 0 && (n & (n - 1)); }
long long ostatok2(const long long n, const long long m) { return m & (n - 1); }
template <typename X>
void SWAP(X& a, X& b) {
  a ^= b;
  b ^= a;
  a ^= b;
}
size_t count_1_in_LL(unsigned long long n) {
  std::size_t i(0);
  for (; n; ++i) n &= n - 1;
  return i;
}
}  // namespace bits
void debug() { cout << endl; }
template <typename H, typename... T>
void debug(H p, T... t) {
  std::cout << p << " ";
  debug(t...);
}
vector<vector<int> > g;
inline void solution() {
  string s;
  cin >> s;
  map<int, int> q;
  string a = "1689";
  for (long long i = 0; i < s.size(); ++i) {
    q[s[i] - '0']++;
  }
  string res = "";
  int mod = 0;
  for (auto x : q) {
    if (x.first != 0) {
      if (x.first == 1 || x.first == 6 || x.first == 8 || x.first == 9) {
        for (long long i = 0; i < x.second - 1; ++i) {
          res += x.first + '0';
          mod *= 10;
          mod += x.first;
          mod %= 7;
        }
      } else {
        for (long long i = 0; i < x.second; ++i) {
          res += x.first + '0';
          mod *= 10;
          mod += x.first;
          mod %= 7;
        }
      }
    }
  }
  mod *= 10000;
  mod %= 7;
  do {
    int cur = stoi(a);
    if ((cur % 7 + mod) % 7 == 0) {
      res += a;
      for (long long i = 0; i < q[0]; ++i) res += "0";
      break;
    }
  } while (next_permutation(a.begin(), a.end()));
  ;
  cout << res;
  ;
}

### Prompt

Create a solution in Cpp for the following problem:

You have number a, whose decimal representation quite luckily contains digits 1, 6, 8, 9. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7.

Number a doesn't contain any leading zeroes and contains digits 1, 6, 8, 9 (it also can contain another digits). The resulting number also mustn't contain any leading zeroes.

Input

The first line contains positive integer a in the decimal record. It is guaranteed that the record of number a contains digits: 1, 6, 8, 9. Number a doesn't contain any leading zeroes. The decimal representation of number a contains at least 4 and at most 106 characters.

Output

Print a number in the decimal notation without leading zeroes — the result of the permutation.

If it is impossible to rearrange the digits of the number a in the required manner, print 0.

Examples

Input

1689


Output

1869


Input

18906


Output

18690

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <typename X>
inline X abs(const X& a) {
  return a < 0 ? -a : a;
}
template <typename X>
inline X sqr(const X& a) {
  return a * a;
}
const int size = 1e5 + 2;
const double eps = 0.0001;
const long double PI = 3.1415926535897932384626433832795;
const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const long long MAX5 = 100001;
const long long MAX6 = 1000001;
const long long MAX17 = 99999999999999999;
const double DMAX = 2e18 + 5;
void solution();
void include_file();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solution();
  return 0;
}
void include_file() {
  ios_base::sync_with_stdio(true);
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
inline bool isPrime(long long n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return true;
}
string ekv(string a) {
  if (a.size() & 1) return a;
  string x = ekv(a.substr(0, a.size() / 2));
  string y = ekv(a.substr(a.size() / 2));
  return min(x + y, y + x);
}
long long cubic_root(long long x) {
  long long l = 0, r = MAX6;
  while (l != r) {
    long long m = (l + r + 1) / 2;
    if (m * m * m > x)
      r = m - 1;
    else
      l = m;
  }
  return l;
}
float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i >> 1);
  x = *(float*)&i;
  x = x * (1.5f - (xhalf * x * x));
  return x;
}
long long gcd(long long a, long long b) {
  while (b ^= a ^= b ^= a = a % b)
    ;
  return a;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
constexpr uint64_t mod = (1ull << 61) - 1;
uint64_t modmul(uint64_t a, uint64_t b) {
  uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
  uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  uint64_t ret =
      (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  ret = (ret & mod) + (ret >> 61);
  ret = (ret & mod) + (ret >> 61);
  return ret - 1;
}
void yes() { cout << "YES"; }
void no() { cout << "NO"; }
void yes(bool res, bool small = false) {
  if (!small) {
    if (res)
      cout << "YES";
    else
      cout << "NO";
  } else {
    if (res)
      cout << "Yes";
    else
      cout << "No";
  }
}
void dabl(double x) { printf("%.10lf", x); }
namespace bits {
template <typename X>
inline X MAX(const X& a, const X& b) {
  return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
}
template <typename X>
inline X MIN(const X& a, const X& b) {
  return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
}
bool check2(const long long n) { return n > 0 && (n & (n - 1)); }
long long ostatok2(const long long n, const long long m) { return m & (n - 1); }
template <typename X>
void SWAP(X& a, X& b) {
  a ^= b;
  b ^= a;
  a ^= b;
}
size_t count_1_in_LL(unsigned long long n) {
  std::size_t i(0);
  for (; n; ++i) n &= n - 1;
  return i;
}
}  // namespace bits
void debug() { cout << endl; }
template <typename H, typename... T>
void debug(H p, T... t) {
  std::cout << p << " ";
  debug(t...);
}
vector<vector<int> > g;
inline void solution() {
  string s;
  cin >> s;
  map<int, int> q;
  string a = "1689";
  for (long long i = 0; i < s.size(); ++i) {
    q[s[i] - '0']++;
  }
  string res = "";
  int mod = 0;
  for (auto x : q) {
    if (x.first != 0) {
      if (x.first == 1 || x.first == 6 || x.first == 8 || x.first == 9) {
        for (long long i = 0; i < x.second - 1; ++i) {
          res += x.first + '0';
          mod *= 10;
          mod += x.first;
          mod %= 7;
        }
      } else {
        for (long long i = 0; i < x.second; ++i) {
          res += x.first + '0';
          mod *= 10;
          mod += x.first;
          mod %= 7;
        }
      }
    }
  }
  mod *= 10000;
  mod %= 7;
  do {
    int cur = stoi(a);
    if ((cur % 7 + mod) % 7 == 0) {
      res += a;
      for (long long i = 0; i < q[0]; ++i) res += "0";
      break;
    }
  } while (next_permutation(a.begin(), a.end()));
  ;
  cout << res;
  ;
}

```