Divisible by Seven

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 numbera contains digits: 1, 6, 8, 9. Number a doesn't contain any leading zeroes. The decimal representation of numbera contains at least 4 and at most 10⁶ 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.

Example

Input

1689

Output

1869

Input

18906

Output

18690

题意：给你一个至少四位的数，里面必包含1，6，8，9可以有其他的数字，通过调整问你能把它变成整除7的数并输出来，并且不带前导0。

思路：里面除了1，6，8，9这一个组合，之外的的数，算他们除7之后的余数假设为haha，要整除7肯定是他们除7之后的余数haha+（1，6，8，9）这个组合除7之后的余数==7才能整除7，用7减去haha就是（1，6，8，9）这个组合要除以7得到的余数，所以我们就要找这个组合怎么组合才能得到这个余数，找到后先把除了（1，6，8，9）这个组合之外的数输出来，然后再输出（1，6，8，9）这个组合，最后把0输出来，就ok了

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int vis[10010000]; int main() { char a[1001000]; scanf("%s",a); memset(vis,0,sizeof(vis)); int mod=0; int l=strlen(a); int p=0; int w=0,e=0,r=0,t=0;//用来标记1，6，8，9这个组合 for(int i=0;i<l;i++) { int we=(a[i]-'0'); if(we==0) { p++; vis[i]=1; continue; } if(we==1&&!w) { w=1; vis[i]=1; continue; } if(we==6&&!e) { vis[i]=1; e=1; continue; } if(we==8&&!r) { r=1; vis[i]=1;; continue; } if(we==9&&!t) { vis[i]=1; t=1; continue; } else mod=(mod*10+we)%7; } mod=(mod*10000)%7; for(int i=0;i<l;i++) { if(!vis[i])//把（1，6，8，9）这一个组合之外的数输出来 { printf("%c",a[i]); } } if(mod==0)//找适合剩余余数的（1，6，8，9）这个组合 { printf("1869"); } else if(mod+1==7) { printf("1968"); } else if(mod+2==7) { printf("1689"); } else if(mod+3==7) { printf("6198"); } else if(mod+4==7) { printf("1698"); } else if(mod+5==7) { printf("1986"); } else if(mod+6==7) { printf("1896"); } while(p--)输出0 { printf("0"); } }