#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
 
// Hàm tìm số nhỏ nhất chỉ chứa {0, 1} và là bội của n
string findSmallestMultiple(int n) {
    // Hàng đợi lưu trữ trạng thái (phần dư, chuỗi nhị phân)
    queue<pair<int, string>> q;
    // Mảng đánh dấu để tránh lặp trạng thái
    vector<bool> visited(n, false);
 
    // Khởi tạo trạng thái ban đầu với "1"
    q.push({1 % n, "1"});
    visited[1 % n] = true;
 
    while (!q.empty()) {
        auto [remainder, binary] = q.front();
        q.pop();
 
        // Nếu phần dư là 0, trả về kết quả
        if (remainder == 0) {
            return binary;
        }
 
        // Sinh các trạng thái tiếp theo bằng cách thêm "0" và "1"
        for (int digit : {0, 1}) {
            int newRemainder = (remainder * 10 + digit) % n;
            if (!visited[newRemainder]) {
                visited[newRemainder] = true;
                q.push({newRemainder, binary + char('0' + digit)});
            }
        }
    }
 
    return ""; // Trường hợp không tìm thấy (không xảy ra với n > 0)
}
 
int main() {
    int n;
    cin >> n;
    cout << findSmallestMultiple(n) << endl;
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBIw6BtIHTDrG0gc+G7kSBuaOG7jyBuaOG6pXQgY2jhu4kgY2jhu6lhIHswLCAxfSB2w6AgbMOgIGLhu5lpIGPhu6dhIG4Kc3RyaW5nIGZpbmRTbWFsbGVzdE11bHRpcGxlKGludCBuKSB7CiAgICAvLyBIw6BuZyDEkeG7o2kgbMawdSB0cuG7ryB0cuG6oW5nIHRow6FpIChwaOG6p24gZMawLCBjaHXhu5dpIG5o4buLIHBow6JuKQogICAgcXVldWU8cGFpcjxpbnQsIHN0cmluZz4+IHE7CiAgICAvLyBN4bqjbmcgxJHDoW5oIGThuqV1IMSR4buDIHRyw6FuaCBs4bq3cCB0cuG6oW5nIHRow6FpCiAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChuLCBmYWxzZSk7CgogICAgLy8gS2jhu59pIHThuqFvIHRy4bqhbmcgdGjDoWkgYmFuIMSR4bqndSB24bubaSAiMSIKICAgIHEucHVzaCh7MSAlIG4sICIxIn0pOwogICAgdmlzaXRlZFsxICUgbl0gPSB0cnVlOwoKICAgIHdoaWxlICghcS5lbXB0eSgpKSB7CiAgICAgICAgYXV0byBbcmVtYWluZGVyLCBiaW5hcnldID0gcS5mcm9udCgpOwogICAgICAgIHEucG9wKCk7CgogICAgICAgIC8vIE7hur91IHBo4bqnbiBkxrAgbMOgIDAsIHRy4bqjIHbhu4Ega+G6v3QgcXXhuqMKICAgICAgICBpZiAocmVtYWluZGVyID09IDApIHsKICAgICAgICAgICAgcmV0dXJuIGJpbmFyeTsKICAgICAgICB9CgogICAgICAgIC8vIFNpbmggY8OhYyB0cuG6oW5nIHRow6FpIHRp4bq/cCB0aGVvIGLhurFuZyBjw6FjaCB0aMOqbSAiMCIgdsOgICIxIgogICAgICAgIGZvciAoaW50IGRpZ2l0IDogezAsIDF9KSB7CiAgICAgICAgICAgIGludCBuZXdSZW1haW5kZXIgPSAocmVtYWluZGVyICogMTAgKyBkaWdpdCkgJSBuOwogICAgICAgICAgICBpZiAoIXZpc2l0ZWRbbmV3UmVtYWluZGVyXSkgewogICAgICAgICAgICAgICAgdmlzaXRlZFtuZXdSZW1haW5kZXJdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIHEucHVzaCh7bmV3UmVtYWluZGVyLCBiaW5hcnkgKyBjaGFyKCcwJyArIGRpZ2l0KX0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiAiIjsgLy8gVHLGsOG7nW5nIGjhu6NwIGtow7RuZyB0w6xtIHRo4bqleSAoa2jDtG5nIHjhuqN5IHJhIHbhu5tpIG4gPiAwKQp9CgppbnQgbWFpbigpIHsKICAgIGludCBuOwogICAgY2luID4+IG47CiAgICBjb3V0IDw8IGZpbmRTbWFsbGVzdE11bHRpcGxlKG4pIDw8IGVuZGw7CiAgICByZXR1cm4gMDsKfQ==

Ng==

6