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 10^6 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

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def main():
	a = input()
	l = len(a)
	book = [0] * 128
	a = list(a)
	for i in range(l):
		a[i] = chr(ord(a[i]) - ord('0'))
		book[ord(a[i])] += 1
	num = 0
	m = 0
	buf = []
	for i in range(1, 10):
		if i in (1, 8, 6, 9):
			for j in range(1, book[i]):
				buf.append(i)
				m = (10 * m + i) % 7
				num += 1
		else:
			for j in range(1, book[i] + 1):
				buf.append(i)
				m = (10 * m + i) % 7
				num += 1
	m = m * 10000 % 7
	mp = [9681, 1896, 9861, 1698, 6891, 6981, 6819]
	buf.append(mp[m])
	num += 4
	buf.append('0' * (l - num))
	print(''.join(map(str, buf)))
main()


S = '1689'
s = input()
Z = s.count('0')
s = s.replace('0', '')
for i in S:
	t = s.index(i)
	s = s[:t] + s[t + 1:]
k = 0
for i in s:
	k = (k * 10 + ord(i) - ord('0')) % 7
for a in S:
	for b in S:
		for c in S:
			for d in S:
				if len(set(a + b + c + d)) == 4 and (k * 10000 + int(a + b + c + d)) % 7 == 0:
					print(s + a + b + c + d + '0' * Z)
					exit()


def end(x):
	if x == 0:
		return '1869'
	if x == 6:
		return '1968'
	if x == 5:
		return '1689'
	if x == 4:
		return '6891'
	if x == 3:
		return '1698'
	if x == 2:
		return '1986'
	if x == 1:
		return '1896'
d = [0] * 10
for c in input():
	d[int(c)] += 1
for i in [1, 6, 8, 9]:
	d[i] -= 1
s = ''
ost = 0
for i in range(10):
	for j in range(d[i]):
		ost = (ost * 10 + i) % 7
ost = ost * 10000 % 7
for c in (1, 2, 3, 4, 5, 6, 7, 8, 9):
	s += str(c) * d[c]
print(s + end(ost) + '0' * d[0])


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi, ceil, log
import math
from itertools import permutations
from copy import deepcopy
from sys import setrecursionlimit

def main():
	a = input().rstrip()
	n = len(a)
	a = Counter(a)
	a['6'] -= 1
	a['1'] -= 1
	a['8'] -= 1
	a['9'] -= 1
	(z, s, y) = (0, [], [1])
	for i in range(n):
		y.append(y[-1] * 10 % 7)
	xx = 1
	for i in a:
		if i != '0':
			x = int(i)
			for j in range(a[i]):
				s.append(i)
				z = (z + x * y[n - xx]) % 7
				xx += 1
	f = 1
	for i in permutations([1, 6, 8, 9]):
		if (z + i[0] * y[n - xx] + i[1] * y[n - xx - 1] + i[2] * y[n - xx - 2] + i[3] * y[n - xx - 3]) % 7 == 0:
			f = 0
			s.extend([str(i[0]), str(i[1]), str(i[2]), str(i[3])])
			break
	if f:
		print(0)
	else:
		s.append('0' * a['0'])
		print(''.join(s))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os, sys, math
from io import BytesIO, IOBase
it = lambda : int(input())
ma = lambda : map(int, input().split(' '))
li = lambda : list(map(int, input().split(' ')))
r = 10 ** 9 + 7

def l_m(a, b):
	x = math.gcd(a, b)
	return a * b // x

def main():
	s = input()
	x = 0
	y = 0
	z = 0
	w = 0
	lis = ['1869', '1968', '1689', '6198', '1698', '1986', '1896']
	counts = [0] * 10
	n = len(s)
	for i in range(n):
		counts[ord(s[i]) - 48] += 1
	counts[6] -= 1
	counts[1] -= 1
	counts[8] -= 1
	counts[9] -= 1
	x = 0
	y = ''
	for i in range(1, 10):
		y += counts[i] * str(i)
		for j in range(counts[i]):
			x = (10 * x + i) % 7
	mod = 4 * x % 7
	f = y + lis[(7 - mod) % 7] + '0' * counts[0]
	print(f)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
n = [int(d) for d in sys.stdin.readline()[:-1]]
for x in [1, 6, 8, 9]:
	for i in range(len(n)):
		if n[i] == x:
			del n[i]
			break
prefix = [1869, 6189, 1689, 6198, 1698, 9861, 1896]
L = sum([n[i] * pow(10, len(n) - i - 1, 7) for i in range(len(n))]) % 7
print(prefix[-L * pow(10, 5 * len(n), 7) % 7], end='')
print(*n, sep='')


n = [int(i) for i in input()]
for x in [1, 6, 8, 9]:
	for i in range(len(n)):
		if n[i] == x:
			del n[i]
			break
prefix = [1869, 6189, 1689, 6198, 1698, 9861, 1896]
res = sum([n[i] * pow(10, len(n) - i - 1, 7) for i in range(len(n))])
print(prefix[-res * pow(10, 5 * len(n), 7) % 7], end='')
print(*n, sep='')


from itertools import permutations
(t, r) = ([0, 1, 4, 6, 5, 2], {i: 0 for i in '0123456789'})
for i in input():
	r[i] += 1
for i in '1689':
	r[i] -= 1
s = a = b = 0
for i in '9876543210':
	(a, b) = (b, (b + r[i]) % 6)
	s += int(i) * (t[b] - t[a])
d = pow(10, b, 7)
for q in permutations('1689'):
	q = ''.join(q)
	if (s + d * int(q)) % 7 == 0:
		print(q + ''.join((i * r[i] for i in '0123456789')))
		break


ans = [1, 6, 8, 9]
rem = []
from collections import *
al = defaultdict(int)
for i in range(len(ans)):
	for j in range(len(ans)):
		for m in range(len(ans)):
			for t in range(len(ans)):
				re = [i, j, m, t]
				if len(set(re)) == 4:
					q = pow(10, 3) * ans[i] + pow(10, 2) * ans[j] + pow(10, 1) * ans[m] + ans[t]
					if al[q % 7] == 0:
						rem.append([q % 7, q])
						al[q % 7] = 1
s = input()
rem.sort()
ans = []
for i in range(len(s)):
	ans.append(int(s[i]))
count = 0
ans.remove(1)
ans.remove(6)
ans.remove(8)
ans.remove(9)
i = 0
while i < len(ans):
	if i == 0:
		while i < len(ans) and ans[i] == 0:
			count += 1
			i += 1
		i += 1
	else:
		i += 1
temp = []
for i in range(count, len(ans)):
	temp.append(ans[i])
fin = 0
if len(temp) == 0:
	s = str(rem[0][1]) + '0' * count
	print(s)
	return
else:
	for i in range(len(temp)):
		fin = fin + pow(10, len(temp) - i - 1, 7) * (temp[i] % 7) % 7
		fin %= 7
	if fin == 0:
		m = ''.join(map(str, temp)) + str(rem[fin][1]) + '0' * count
	if fin == 1:
		m = ''.join(map(str, temp)) + str(rem[3][1]) + '0' * count
	if fin == 2:
		m = ''.join(map(str, temp)) + str(rem[6][1]) + '0' * count
	if fin == 3:
		m = ''.join(map(str, temp)) + str(rem[2][1]) + '0' * count
	if fin == 4:
		m = ''.join(map(str, temp)) + str(rem[5][1]) + '0' * count
	if fin == 5:
		m = ''.join(map(str, temp)) + str(rem[1][1]) + '0' * count
	if fin == 6:
		m = ''.join(map(str, temp)) + str(rem[4][1]) + '0' * count
	print(m)


import sys
input = sys.stdin.readline
a = input().rstrip()
s = ['1869', '1968', '1689', '6198', '1698', '1986', '1896']
cnt = [0] * 10
for i in range(len(a)):
	cnt[int(a[i])] += 1
cnt[1] -= 1
cnt[6] -= 1
cnt[8] -= 1
cnt[9] -= 1
ans = []
m = 0
for i in range(1, 10):
	while cnt[i] > 0:
		m = (10 * m + i) % 7
		ans.append(str(i))
		cnt[i] -= 1
need_m = (7 - m * 10 ** 4 % 7) % 7
ans.append(s[need_m])
ans.extend(['0'] * cnt[0])
print(''.join(ans))


import itertools
digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
numdict = {'all': '1869234570', '-1': '2345896', '-2': '1345869', '-3': '1245986', '-4': '1235689', '-5': '1234968', '-6': '1235948', '-8': '1234569', '-9': '1234856'}

def list2num(numlist):
	num = 0
	for digit in numlist:
		num = num * 10 + digit
	return num

def div7(numlist):
	pailie = itertools.permutations(numlist)
	flag = 0
	for yuanshu in pailie:
		num = list2num(yuanshu)
		if num % 7 == 0:
			flag = 1
			return num
			break
	if flag == 0:
		return 0

def pre_num(num_string):
	count = []
	for i in range(10):
		if str(i) in '1689':
			count.append(num_string.count(str(i)) - 1)
		else:
			count.append(num_string.count(str(i)))
	return count

def simulinkinput():
	tmp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	tmp = tmp * 5
	for i in range(10, 40):
		zhuhe = itertools.combinations(tmp, i)
		for yuanshu in zhuhe:
			num_string = str(list2num(yuanshu)) + '1689'
			main(num_string)

def count2num(numlist):
	tmplist = []
	for i in range(1, len(numlist)):
		if numlist[i] > 0:
			tmplist.append(i)
	return tmplist

def main():
	num_string = input()
	result_string = ['', '111111', '222222', '333333', '444444', '555555', '666666', '777777', '888888', '999999']
	res_list = [1, 8, 6, 9]
	count = []
	count = pre_num(num_string)
	result = ''
	for i in range(1, 10):
		if count[i] >= 6:
			loop = count[i] // 6
			result = result + result_string[i] * loop
			count[i] = count[i] % 6
	mincount = min(count[1:])
	if mincount > 0:
		result = result + '186923457' * mincount
		for i in range(1, 10):
			count[i] = count[i] - mincount
	for i in range(9):
		numzhlist = count2num(count)
		mincount = min(count[1:])
		tmpstring = div7(numzhlist)
		if tmpstring != 0:
			result = result + str(tmpstring) * mincount
			for j in numzhlist:
				count[j] = count[j] - mincount
		else:
			break
	for i in range(1, 10):
		for j in range(count[i]):
			res_list.append(i)
	resnum = div7(res_list)
	if resnum == 0:
		exit('0')
	else:
		result = result + str(resnum) + '0' * count[0]
	print(result)
main()


from os import path
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def ceil(a, b):
	return (a + b - 1) // b
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')
test = 0

def solve():
	x = ['1869', '6198', '1896', '1689', '1986', '1968', '8691']
	freq = [0] * 10
	s = si()
	for i in s:
		freq[int(i)] += 1
	freq[1] -= 1
	freq[6] -= 1
	freq[8] -= 1
	freq[9] -= 1
	res = ''
	cur = 0
	for i in range(1, 10):
		for j in range(freq[i]):
			cur *= 10
			cur += i
			cur %= 7
	for i in range(1, 10):
		print(str(i) * freq[i], end='')
	print(x[cur], end='')
	print('0' * freq[0])

def __starting_point():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
	t = 1
	if test:
		t = ii()
	for _ in range(t):
		solve()
__starting_point()


import sys
from math import *
from fractions import gcd
readints = lambda : map(int, input().strip('\n').split())
n = input().strip('\n')
from itertools import permutations
perms = [''.join(p) for p in permutations('1689')]
mod = {}
for p in perms:
	p = int(p)
	mod[p % 7] = p
freq = [0] * 10
for d in n:
	d = int(d)
	freq[d] += 1
for d in (1, 6, 8, 9):
	freq[d] -= 1
m = 0
for i in range(1, 10):
	for _ in range(freq[i]):
		m = (10 * m + i) % 7
suf = ''
for p in mod.values():
	cur = int(str(m) + str(p))
	if cur % 7 == 0:
		suf = str(p)
		break
ans = ''
for i in range(1, 10):
	ans += str(i) * freq[i]
ans += suf
ans += '0' * freq[0]
print(ans)


import os, sys
from io import BytesIO, IOBase

def main():
	x = input().strip()
	ls = []
	fl = [0, 0, 0, 0]
	st = '1689'
	for i in x:
		if i in st and (not fl[st.index(i)]):
			fl[st.index(i)] = 1
			continue
		ls.append(i)
	ls1 = ls[::-1]
	perm = ['1869', '1968', '1689', '6198', '1698', '1986', '1896']
	val = [1, 3, 2, 6, 4, 5]
	rem = 0
	for i in range(len(ls1)):
		rem += int(ls1[i]) * val[i % 6] % 7
		rem %= 7
	ls = list(perm[(7 - rem) * pow(pow(10, len(ls1), 7), 5, 7) % 7]) + ls
	print(''.join(ls))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(p, t) = ({}, input())
for i in '0123456789':
	p[i] = 0
for i in t:
	p[i] += 1
for i in '1689':
	p[i] -= 1
q = [0] * 7
r = pow(10, (len(t) - 4) % 6, 7)
for (i, j) in enumerate([9681, 6819, 6981, 6891, 8691, 9861, 1896]):
	q[i * r % 7] = j
s = [0] + [int('1' * i) % 7 for i in range(1, 6)]
a = b = d = 0
for i in '0123456789':
	b = (a + p[i]) % 6
	d -= (s[b] - s[a]) * int(i) % 7
	a = b
print(str(q[d % 7]) + ''.join((i * p[i] for i in '9876543210')))


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p + p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	n = input().rstrip()
	b = [0] * 10
	for x in n:
		b[int(x)] += 1
	for x in '1689':
		b[int(x)] -= 1
	y = ['1869', '1968', '9816', '6198', '1698', '1986', '1896', '1869']
	total = 0
	for i in range(1, 10):
		for j in range(b[i]):
			total = (total * 10 + i) % 7
		print(str(i) * b[i], end='')
	total = total * 10000 % 7
	print(y[7 - total] + '0' * b[0])
for _ in range(1):
	solve()


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
from itertools import permutations, combinations
from collections import *
from bisect import *
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
val = [1, 6, 8, 9]
rem = [None] * 7
for v in permutations(val):
	md = 0
	for i in range(len(v)):
		md += v[i] * 10 ** i
	rem[md % 7] = md
used = set([1, 8, 6, 9])
zeros = 0
ans = []
cmd = 0
for v in gbs():
	if v in used:
		used.remove(v)
		continue
	if v == 0:
		zeros += 1
		continue
	cmd += v % 7 * pow(10, len(ans) + 4, 7) % 7
	if cmd >= 7:
		cmd %= 7
	ans.append(str(v))
ans.reverse()
print(''.join(ans) + str(rem[(7 - cmd) % 7]) + '0' * zeros)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def check_div(s):
	ans = 0
	j = 0
	for i in range(len(s) - 1, -1, -1):
		ans += s[i] * pow(10, j, 7)
		ans %= 7
		j += 1
	return ans % 7
for _ in range(int(input()) if not True else 1):
	s = [int(k) for k in input()]
	(a, b, c, d) = (0, 0, 0, 0)
	zero = 0
	s2 = []
	for i in s:
		if i == 0:
			zero += 1
		elif i == 1 and (not a):
			a += 1
		elif i == 6 and (not b):
			b += 1
		elif i == 8 and (not c):
			c += 1
		elif i == 9 and (not d):
			d += 1
		else:
			s2 += [i]
	s22 = check_div(s2)
	fk = [[1, 6, 8, 9], [1, 6, 9, 8], [1, 8, 6, 9], [1, 8, 9, 6], [1, 9, 6, 8], [1, 9, 8, 6], [6, 1, 8, 9], [6, 1, 9, 8], [6, 8, 1, 9], [6, 8, 9, 1], [6, 9, 1, 8], [6, 9, 8, 1], [8, 1, 6, 9], [8, 1, 9, 6], [8, 6, 1, 9], [8, 6, 9, 1], [8, 9, 1, 6], [8, 9, 6, 1], [9, 1, 6, 8], [9, 1, 8, 6], [9, 6, 1, 8], [9, 6, 8, 1], [9, 8, 1, 6], [9, 8, 6, 1]]
	for f in fk:
		if (s22 * 10 ** 4 + check_div(f)) % 7 == 0:
			print(''.join((str(k) for k in s2 + f + [0] * zero)))
			quit()


a = input()
cnt = [0] * 10
for i in (1, 6, 8, 9):
	cnt[i] = -1
for i in a:
	cnt[int(i)] += 1
mod = [1869, 1968, 9816, 6198, 1698, 1986, 1896, 1869]
modCnt = 0
for i in range(1, 10):
	for j in range(cnt[i]):
		modCnt = (modCnt * 3 + i) % 7
	print(str(i) * cnt[i], end='')
modCnt = 10000 * modCnt % 7
print(str(mod[7 - modCnt]) + '0' * cnt[0])


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True
s = input()
f = [0] * 10
mod = [1869, 8961, 6981, 6198, 1698, 9861, 1896]
for i in s:
	f[int(i)] += 1
a = ''
cm = 0
for i in s:
	if i != '0':
		n = int(i)
		if n == 1 or n == 6 or n == 8 or (n == 9):
			if f[n] > 1:
				cm = (cm * 10 + n) % 7
				f[n] -= 1
				print(i, end='')
		else:
			cm = (cm * 10 + n) % 7
			f[n] -= 1
			print(i, end='')
for i in range(0, 4):
	cm = cm * 10 % 7
if cm == 0:
	print(str(mod[cm]), end='')
	print('0' * f[0])
else:
	print(str(mod[7 - cm]), end='')
	print('0' * f[0])


s = input()
cnt = [0] * 10
for c in s:
	cnt[int(c)] += 1
if cnt[1] == 1 and cnt[6] == 1 and (cnt[8] == 1) and (cnt[9] == 1) and (sum(cnt) == cnt[0] + 4):
	print('9618' + '0' * cnt[0])
else:
	cnt[1] -= 1
	cnt[6] -= 1
	cnt[8] -= 1
	cnt[9] -= 1
	s = []
	mod = 0
	for d in range(1, 10):
		for i in range(cnt[d]):
			s += [str(d)]
			mod *= 10
			mod += d
			mod %= 7
	import itertools
	a = [1, 6, 8, 9]
	for p in itertools.permutations(a):
		x = p[0] * 1000 + p[1] * 100 + p[2] * 10 + p[3]
		if (mod * 10000 + x) % 7 == 0:
			res = ''.join(s)
			res += str(x) + '0' * cnt[0]
			print(res)
			break


a = input()
b = [0] * 10
total = 0
for i in a:
	b[int(i)] += 1
for i in [1, 6, 8, 9]:
	b[i] -= 1
for i in range(1, 10):
	for j in range(b[i]):
		total = (total * 10 + i) % 7
	print(str(i) * b[i], end='')
total = 10000 * total % 7
z = ['1869', '6189', '9186', '6198', '8691', '9168', '1896', '1869']
print(z[7 - total] + '0' * b[0])