Một số nguyên dương X gồm n chữ số dạng (a1a2...an ) có trọng số S(X) được tính theo công thức: S(X)=1xa1 + 2xa2 + ... + nxan. Ví dụ: X=2025 có trọng số là S(2025)=1x2+2x0+3x2+4×5=28.

Yêu cầu:

Cho số nguyên dương X trong đó có một chữ số bị mờ biểu diễn bằng dấu '?'. Hãy tìm chữ số có giá trị nhỏ nhất trong các chữ số từ '0' đến '9' để thay vào vị trí dấu '?' sao cho S(X) chia hết cho 7.

Dữ liệu:

Vào từ tệp CAU1.INP chứa số nguyên dương X (X < 10^100) trong đó có 1 chữ số bị mờ biểu diễn bằng dấu '?'.

Kết quả:

Ghi ra tệp CAU1.OUT một chữ số nhỏ nhất có thể thay vào dấu '?', nếu không tồn tại chữ số nào thoả mãn thì ghi -1. Số X không được chứa chữ số '0' vô nghĩa ở đầu.

Ví dụ 1:

CAU1.INP

202?

CAU1.OUT

5

Giải thích: Số 2025 có S(2025) = 28 chia hết cho 7.

Ví dụ 2:

CAU1.INP

?7

CAU1.OUT

7

Giải thích: Vì dấu '?' đứng đầu không thể thay bằng chữ số 0, nên X = 77 có S(77)= 21 chia hết cho 7.

Ví dụ 3:

CAU1.INP

800000?

CAU1.OUT

-1

Giải thích: Không có chữ số nào thay thế dấu '?' thoả mãn S(X) chia hết cho 7.