Smallest All-X Multiple

Let us call a decimal number that consists of a single repeated digit an all-X number (for example, 22222, 3333, 7777 etc.).

Given an integer \(n\), find the smallest multiple of \(n\) that is an all-X number. Formally, find the smallest positive integer \(m\) and a digit \(d\) (\(1\le d\le 9\)) such that \(n\) divides

\[ d\times \frac{10^m-1}{9}\]

If such a number exists, output the number modulo \(998244353\). Otherwise, output \(-1\).

inputFormat

The input consists of a single integer \(n\).

outputFormat

Output a single integer: the smallest all-X multiple of \(n\) modulo \(998244353\) if it exists, otherwise \(-1\).

sample

1

1