#include using namespace std; using ll = long long; #ifdef LOCAL #include #else #define debug(...) #endif ll naive(ll N) { // 1e15 以下の iwi 数を全探索 string pre, suf, s1, s2; for (ll i = 1e4;; i++) { pre = to_string(i); suf = pre; reverse(suf.begin(), suf.end()); s1 = pre + suf + '9'; s2 = pre + suf.substr(1) + '9'; ll n1 = stoll(s1), n2 = stoll(s2); if (n1 > 1e15 && n2 > 1e15) break; if (n1 % N == 0) return n1; if (n2 % N == 0) return n2; } assert(false); return 0; } void test() { // 100 以下の iwi 数を全探索 string pre, suf, s1, s2; for (ll i = 1; i <= 100; i++) { pre = to_string(i); suf = pre; reverse(suf.begin(), suf.end()); s1 = pre + suf + '9'; s2 = pre + suf.substr(1) + '9'; ll n1 = stoll(s1), n2 = stoll(s2); debug(n1, naive(n1), n2, naive(n2)); } } using i128 = __int128_t; i128 power(i128 x, i128 n) { i128 res = i128{1}; while (n) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } i128 power(i128 x, i128 n, const i128 mod) { i128 res = i128{1}; x %= mod; while (n) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); // test(); // N を有限回繋げたものが N の倍数になるのでは? int N; cin >> N; string S = to_string(N), iwi = S; ll mod = 0; while (true) { iwi += S; mod = mod * power(10, ssize(S), N) % N; if (ssize(iwi) > 9 && mod == 0) { cout << iwi << "\n"; return 0; } } }