The very same Munchhausen

题意翻译

设 $S(x)$ 表示 $x$ 的数位和，给定 $a$ ，求一个 $n$ ，使得 $S(an)=S(n)/a$ ，无解输出 $-1$ ，要求 $n$ 最多只能含 $5*10^5$ 个数字，保证要么无解，要么有符合条件的 $n$。

题目描述

A positive integer $ a $ is given. Baron Munchausen claims that he knows such a positive integer $ n $ that if one multiplies $ n $ by $ a $ , the sum of its digits decreases $ a $ times. In other words, $ S(an) = S(n)/a $ , where $ S(x) $ denotes the sum of digits of the number $ x $ . Find out if what Baron told can be true.

输入输出格式

输入格式

The only line contains a single integer $ a $ ( $ 2 \le a \le 10^3 $ ).

输出格式

If there is no such number $ n $ , print $ -1 $ . Otherwise print any appropriate positive integer $ n $ . Your number must not consist of more than $ 5\cdot10^5 $ digits. We can show that under given constraints either there is no answer, or there is an answer no longer than $ 5\cdot10^5 $ digits.

输入输出样例

输入样例 #1

2

输出样例 #1

6

输入样例 #2

3

输出样例 #2

6669

输入样例 #3

10

输出样例 #3

-1