G. Food Rations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Shannon and $$$6$$$ of her friends are planning an *extended* camping trip. They plan on packing rations in order to last them for the entirety of their trip. However, they don't know exactly how long they plan to remain camping so Shannon decides to concatenate a lot of randomly generated digits to make the number $$$s$$$ and pack $$$s$$$ rations.

However, she quickly realizes that $$$s$$$ isn't divisible evenly by $$$7$$$. Her friend group is highly competitive for food and refuse to split rations or allow one person to get more rations than another person. Thus, Shannon needs to pack a number that is perfectly divisible by $$$7$$$ and decides to simply rearrange the digits of $$$s$$$. Luckily, she finds that $$$s$$$ at least one of each of the following digits: 1, 6, 8, and 9. Help Shannon permute the digits of her number $$$s$$$ to figure out the number of rations to pack for the group's trip!

Input

The first and only line will contain the positive number $$$s$$$ which does not have any leading zeros and contains at least one of each of the following digits: 1, 6, 8, and 9. It is also guaranteed that $$$1689 \leq s \leq 10^{10^6}$$$ ($$$s$$$ will have at least $$$4$$$ digits and at most $$$10^{6}$$$ digits).

Output

Output the result of the permutation aka the number of rations that Shannon should bring so that it will be divisible by $$$7$$$. The number should not contain any leading zeros but it should still use the same number of each digit as $$$s$$$.

If it is not possible to permute the digits to create a number divisible by $$$7$$$, output $$$-1$$$.

Examples
Input
1689
Output
1869
Input
8589157262
Output
2255781689