import java.util.*;

public class Euler698 {
    static final long kTargetN = 111111111111222333L;
    static final long kMod = 123123123L;
    static final int kIs123Limit = 5000;

    static long satAdd(long a, long b, long cap) {
        long v = a + b;
        if (v < 0 || v > cap)
            return cap + 1;
        return v;
    }

    static long satMul(long a, long b, long cap) {
        if (a == 0 || b == 0)
            return 0;
        if (a > cap / b + 1)
            return cap + 1;
        long v = a * b;
        if (v > cap)
            return cap + 1;
        return v;
    }

    static boolean[] buildIs123(int limit) {
        boolean[] is123 = new boolean[limit + 1];
        is123[1] = true;
        for (int x = 2; x <= limit; ++x) {
            String s = Integer.toString(x);
            int c1 = 0, c2 = 0, c3 = 0;
            boolean valid = true;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '1')
                    c1++;
                else if (ch == '2')
                    c2++;
                else if (ch == '3')
                    c3++;
                else {
                    valid = false;
                    break;
                }
            }
            if (!valid)
                continue;
            if ((c1 == 0 || is123[c1]) && (c2 == 0 || is123[c2]) && (c3 == 0 || is123[c3])) {
                is123[x] = true;
            }
        }
        return is123;
    }

    static class Nth123Solver {
        long cap;
        boolean[] is123;
        List<long[]> choose = new ArrayList<>();
        int length = 0;
        HashMap<Long, Long> memo = new HashMap<>();

        Nth123Solver(long cap, boolean[] is123) {
            this.cap = cap;
            this.is123 = is123;
            choose.add(new long[] { 1L });
        }

        void ensureChoose(int n) {
            while (choose.size() <= n) {
                int m = choose.size();
                long[] row = new long[m + 1];
                row[0] = 1L;
                row[m] = 1L;
                long[] prev = choose.get(m - 1);
                for (int k = 1; k < m; ++k) {
                    row[k] = satAdd(prev[k - 1], prev[k], cap);
                }
                choose.add(row);
            }
        }

        long multinomial(int n, int a, int b) {
            ensureChoose(n);
            long first = choose.get(n)[a];
            long second = choose.get(n - a)[b];
            return satMul(first, second, cap);
        }

        long countLength(int length) {
            long total = 0;
            for (int a = 0; a <= length; ++a) {
                if (a > 0 && !is123[a])
                    continue;
                for (int b = 0; b + a <= length; ++b) {
                    int c = length - a - b;
                    if (b > 0 && !is123[b])
                        continue;
                    if (c > 0 && !is123[c])
                        continue;
                    if (a == 0 && b == 0 && c == 0)
                        continue;
                    total = satAdd(total, multinomial(length, a, b), cap);
                    if (total > cap)
                        return cap + 1;
                }
            }
            return total;
        }

        long packState(int pos, int u1, int u2, int u3) {
            return ((long) pos << 48) | ((long) u1 << 32) | ((long) u2 << 16) | u3;
        }

        long countWithPrefix(int pos, int u1, int u2, int u3) {
            long key = packState(pos, u1, u2, u3);
            if (memo.containsKey(key))
                return memo.get(key);

            int rem = length - pos;
            long total = 0;

            for (int A = u1; A <= length; ++A) {
                if (A > 0 && !is123[A])
                    continue;
                int maxB = length - A;
                if (u2 > maxB)
                    continue;
                for (int B = u2; B <= maxB; ++B) {
                    int C = length - A - B;
                    if (C < u3)
                        continue;
                    if (B > 0 && !is123[B])
                        continue;
                    if (C > 0 && !is123[C])
                        continue;

                    int a = A - u1;
                    int b = B - u2;
                    int c = C - u3;
                    if (a + b + c != rem)
                        continue;

                    total = satAdd(total, multinomial(rem, a, b), cap);
                    if (total > cap) {
                        memo.put(key, cap + 1);
                        return cap + 1;
                    }
                }
            }

            memo.put(key, total);
            return total;
        }

        String solveStr(long n) {
            long cumulative = 0;
            length = 0;

            while (true) {
                length++;
                long count = countLength(length);
                if (satAdd(cumulative, count, cap) >= n) {
                    break;
                }
                cumulative += count;
            }

            long rankInLength = n - cumulative;
            memo.clear();

            int used1 = 0, used2 = 0, used3 = 0;
            StringBuilder out = new StringBuilder(length);

            for (int pos = 0; pos < length; ++pos) {
                for (int d = 1; d <= 3; ++d) {
                    int n1 = used1 + (d == 1 ? 1 : 0);
                    int n2 = used2 + (d == 2 ? 1 : 0);
                    int n3 = used3 + (d == 3 ? 1 : 0);

                    long cnt = countWithPrefix(pos + 1, n1, n2, n3);
                    if (rankInLength > cnt) {
                        rankInLength -= cnt;
                    } else {
                        out.append((char) ('0' + d));
                        used1 = n1;
                        used2 = n2;
                        used3 = n3;
                        break;
                    }
                }
            }
            return out.toString();
        }
    }

    public static String solve() {
        boolean[] is123 = buildIs123(kIs123Limit);
        Nth123Solver solver = new Nth123Solver(kTargetN, is123);
        String valStr = solver.solveStr(kTargetN);

        long value = 0;
        for (int i = 0; i < valStr.length(); ++i) {
            value = (value * 10 + (valStr.charAt(i) - '0')) % kMod;
        }
        return Long.toString(value);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}