import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

public class Euler943 {
    static final long kN = 22332223332233L;
    static final long kMod = 2233222333L;
    static final int kMinValue = 2;
    static final int kMaxValue = 223;
    static final int kMaxDepth = 61;

    static class Summary {
        long count_a;
        long count_b;
        long next_state;

        Summary(long count_a, long count_b, long next_state) {
            this.count_a = count_a;
            this.count_b = count_b;
            this.next_state = next_state;
        }

        long total() {
            return count_a + count_b;
        }
    }

    static class KolakoskiPrefixCounter {
        int a;
        int b;
        Map<Long, Summary> memo = new HashMap<>(32768);

        KolakoskiPrefixCounter(int a, int b) {
            this.a = a;
            this.b = b;
        }

        long cacheKey(long state, int depth) {
            return state + (4L << depth);
        }

        Summary evaluateBlock(long state, int depth, long budget) {
            long length_mask = 2L << depth;
            long bit = state & length_mask;
            long run_length = (bit != 0) ? (long) b : (long) a;
            long take = Math.min(run_length, budget);

            if (depth == 0) {
                long count_a = 0;
                long count_b = 0;
                if ((state & 1L) == 0L) {
                    count_a = take;
                } else {
                    count_b = take;
                }
                long next_state = state ^ 1L;
                return new Summary(count_a, count_b, next_state);
            }

            long produced_a = 0;
            long produced_b = 0;
            long child_state = state ^ bit;

            for (long i = 0; i < take; ++i) {
                long key = cacheKey(child_state, depth - 1);
                Summary child = memo.get(key);
                if (child != null) {
                    long cached_total = child.total();
                    if (produced_a + produced_b + cached_total > budget) {
                        child = evaluateBlock(child_state, depth - 1, budget - (produced_a + produced_b));
                    }
                } else {
                    child = evaluateBlock(child_state, depth - 1, budget - (produced_a + produced_b));
                }
                produced_a += child.count_a;
                produced_b += child.count_b;
                child_state = child.next_state;
            }

            long out_next_state = child_state ^ bit ^ (1L << depth);
            Summary out = new Summary(produced_a, produced_b, out_next_state);
            memo.put(cacheKey(state, depth), out);
            return out;
        }

        Summary evaluatePrefix(long n) {
            for (int depth = 0; depth <= kMaxDepth; ++depth) {
                Summary s = evaluateBlock(0, depth, n);
                if (s.total() >= n) {
                    return s;
                }
            }
            throw new RuntimeException("exceeded max depth");
        }
    }

    static long computeT(int a, int b, long n) {
        KolakoskiPrefixCounter counter = new KolakoskiPrefixCounter(a, b);
        Summary s = counter.evaluatePrefix(n);
        return s.count_a * a + s.count_b * b;
    }

    public static String solve() {
        AtomicInteger nextA = new AtomicInteger(kMinValue);
        int numThreads = Runtime.getRuntime().availableProcessors();
        if (numThreads == 0)
            numThreads = 4;

        long[] partial = new long[numThreads];
        Thread[] workers = new Thread[numThreads];

        for (int tid = 0; tid < numThreads; ++tid) {
            final int tIdFinal = tid;
            workers[tid] = new Thread(() -> {
                long local = 0;
                while (true) {
                    int a = nextA.getAndIncrement();
                    if (a > kMaxValue)
                        break;

                    for (int b = kMinValue; b <= kMaxValue; ++b) {
                        if (a == b)
                            continue;
                        local += computeT(a, b, kN) % kMod;
                        if (local >= kMod) {
                            local %= kMod;
                        }
                    }
                }
                partial[tIdFinal] = local % kMod;
            });
            workers[tid].start();
        }

        for (Thread worker : workers) {
            try {
                worker.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        long answer = 0;
        for (long part : partial) {
            answer += part;
            answer %= kMod;
        }
        return Long.toString(answer);
    }

    public static void main(String[] args) {
        if (computeT(2, 3, 10) != 25L || computeT(3, 4, 20) != 70L) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}