Problem 403

S(10^12) mod 10^8. All polys evaluated mod 24*(2*10^8) then /24.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 403
# S(10^12) mod 10^8. All polys evaluated mod 24*(2*10^8) then /24.

import euler.nt { isqrt }

function modmul(a: i64, b: i64, mod: i64) -> i64 {
    let r: i128 = (a as i128) * (b as i128) % (mod as i128)
    if r < (0 as i128) { return (r + (mod as i128)) as i64 }
    return r as i64
}

function modadd(a: i64, b: i64, mod: i64) -> i64 {
    let mut s: i64 = a + b
    s = s % mod
    if s < 0 { s = s + mod }
    return s
}

function g_mod(n: i64, m2: i64) -> i64 {
    # g(n)=(n^3+5n+6)/6  ; work mod 6*m2
    let mod: i64 = 6 * m2
    let n1: i64 = n % mod
    if n1 < 0 { n1 = n1 + mod }
    let n2: i64 = modmul(n1, n1, mod)
    let n3: i64 = modmul(n2, n1, mod)
    let num: i64 = modadd(modadd(n3, modmul(5, n1, mod), mod), 6, mod)
    return num / 6
}

function G_mod(n: i64, m2: i64) -> i64 {
    if n < 0 { return 0 }
    let mod: i64 = 24 * m2
    let n1: i64 = n % mod
    let n2: i64 = modmul(n1, n1, mod)
    let n3: i64 = modmul(n2, n1, mod)
    let n4: i64 = modmul(n2, n2, mod)
    let mut num: i64 = n4
    num = modadd(num, modmul(2, n3, mod), mod)
    num = modadd(num, modmul(11, n2, mod), mod)
    num = modadd(num, modmul(34, n1, mod), mod)
    num = modadd(num, 24, mod)
    return num / 24
}

function H_mod(n: i64, m2: i64) -> i64 {
    if n < 0 { return 0 }
    let mod: i64 = 24 * m2
    let n1: i64 = n % mod
    # s1 = n(n+1)/2
    let s1_num: i64 = modmul(n1, n1 + 1, 2 * mod)
    # use exact division carefully via mod 2*mod then /2 - ensure even
    let s1: i64 = (s1_num % (2 * mod)) / 2
    s1 = s1 % mod
    # s2 = n(n+1)(2n+1)/6
    let t2: i64 = modmul(modmul(n1, n1 + 1, 6 * mod), (2 * n1 + 1) % (6 * mod), 6 * mod)
    let s2: i64 = t2 / 6
    s2 = s2 % mod
    let s3: i64 = modmul(s1, s1, mod)
    # s4 = n(n+1)(2n+1)(3n^2+3n-1)/30
    let u: i64 = modmul(n1, n1 + 1, 30 * mod)
    u = modmul(u, (2 * n1 + 1) % (30 * mod), 30 * mod)
    let v: i64 = (modmul(3, modmul(n1, n1, 30 * mod), 30 * mod) + modmul(3, n1, 30 * mod) - 1) % (30 * mod)
    if v < 0 { v = v + 30 * mod }
    let t4: i64 = modmul(u, v, 30 * mod)
    let s4: i64 = t4 / 30
    s4 = s4 % mod
    let mut num: i64 = s4
    num = modadd(num, modmul(2, s3, mod), mod)
    num = modadd(num, modmul(11, s2, mod), mod)
    num = modadd(num, modmul(34, s1, mod), mod)
    num = modadd(num, modmul(24, n1 + 1, mod), mod)
    return num / 24
}

function sum_G_mod(l: i64, r: i64, m2: i64) -> i64 {
    if l > r { return 0 }
    let mut v: i64 = H_mod(r, m2) - H_mod(l - 1, m2)
    v = v % m2
    if v < 0 { v = v + m2 }
    return v
}

function min64(a: i64, b: i64) -> i64 {
    if a < b { return a }
    return b
}

function main() -> i32 {
    let MOD: i64 = 100000000
    let M2: i64 = 2 * MOD
    let N: i64 = 1000000000000
    let s: i64 = isqrt(N)
    let mut total: i64 = (2 * G_mod(N, M2) - 1) % M2
    if total < 0 { total = total + M2 }

    if N >= 1 {
        let f1: i64 = (G_mod(N + 1, M2) + G_mod(N - 2, M2) - 1) % M2
        if f1 < 0 { f1 = f1 + M2 }
        total = (total + 2 * f1) % M2
    }
    if N >= 2 {
        let fn: i64 = (g_mod(N, M2) + g_mod(N + 1, M2)) % M2
        total = (total + 2 * fn) % M2
    }

    let hi: i64 = min64(s, N - 1)
    if hi >= 2 {
        let mut small_sum: i64 = 0
        let mut p: i64 = 2
        while p <= hi {
            let m: i64 = N / p
            let term: i64 = (G_mod(m + p, M2) + G_mod(m - p, M2) - 1) % M2
            if term < 0 { term = term + M2 }
            small_sum = (small_sum + term) % M2
            p = p + 1
        }
        total = (total + 2 * small_sum) % M2
    }

    let mut large_sum: i64 = 0
    let mut m: i64 = 1
    while m <= s {
        let mut l: i64 = N / (m + 1) + 1
        let r: i64 = N / m
        if r > s {
            if l <= s { l = s + 1 }
            if l <= r {
                let mut term: i64 = 0
                if r == N && N >= l {
                    if l <= N - 1 {
                        term = (sum_G_mod(l + m, N - 1 + m, M2) - sum_G_mod(l - m - 1, N - 1 - m - 1, M2)) % M2
                    }
                } else {
                    term = (sum_G_mod(l + m, r + m, M2) - sum_G_mod(l - m - 1, r - m - 1, M2)) % M2
                }
                if term < 0 { term = term + M2 }
                large_sum = (large_sum + term) % M2
            }
        }
        m = m + 1
    }
    total = (total + 2 * large_sum) % M2
    let diag: i64 = 2 * min64(N / 2, isqrt(N)) + 1
    total = (total + diag % M2) % M2
    let ans: i64 = (total / 2) % MOD
    printf("%lld\n", ans)
    return 0
}

Generated C

#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
    while (flow_temp_head) {
        flow_temp_node* n = flow_temp_head;
        flow_temp_head = n->next;
        free(n);
    }
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
    flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
    if (!node) return NULL;
    node->next = flow_temp_head;
    flow_temp_head = node;
    if (!flow_temp_atexit_set) {
        flow_temp_atexit_set = 1;
        atexit(flow_temp_free_all);
    }
    return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
    size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
    char* r = (char*)flow_temp_alloc(la + lb + 1);
    if (!r) return NULL;
    if (la) memcpy(r, a, la);
    if (lb) memcpy(r + la, b, lb);
    r[la + lb] = '\0';
    return r;
}

#define __flow_in_arr(arr, val) __extension__ ({ \
    int _found = 0; \
    size_t _n = sizeof(arr)/sizeof((arr)[0]); \
    for (size_t _i = 0; _i < _n; _i++) { \
        if ((arr)[_i] == (val)) { _found = 1; break; } \
    } _found; })

/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
    fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
    abort();
#if defined(__GNUC__) || defined(__clang__)
    __builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")

#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif

#include <math.h>

void* _ui_state = NULL;

static inline float i32_to_f32(int32_t v) { return (float)v; }

/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }

int64_t gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t modmul_i64_i64_i64(int64_t a, int64_t b, int64_t mod);
int64_t modadd_i64_i64_i64(int64_t a, int64_t b, int64_t mod);
int64_t g_mod_i64_i64(int64_t n, int64_t m2);
int64_t G_mod_i64_i64(int64_t n, int64_t m2);
int64_t H_mod_i64_i64(int64_t n, int64_t m2);
int64_t sum_G_mod_i64_i64_i64(int64_t l, int64_t r, int64_t m2);
int64_t min64_i64_i64(int64_t a, int64_t b);
int32_t main(void);

int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
    int64_t a = a0;
    int64_t b = b0;
    while (b != 0) {
        int64_t t = FLOW_CHECKED_MOD((a), (b));
        a = b;
        b = t;
    }
    return a;
}

int64_t lcm_i64_i64(int64_t a, int64_t b) {
    if ((a == 0 || b == 0)) {
        return 0;
    }
    return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}

int64_t isqrt_i64(int64_t n) {
    if (n < 2) {
        return n;
    }
    int64_t x = n;
    int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
    while (y < x) {
        x = y;
        y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
    }
    return x;
}

int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
    int64_t a = FLOW_CHECKED_MOD((a0), (mod));
    int64_t b = FLOW_CHECKED_MOD((b0), (mod));
    int64_t result = 0;
    while (b > 0) {
        if (FLOW_CHECKED_MOD((b), (2)) == 1) {
            result = FLOW_CHECKED_MOD(((result + a)), (mod));
        }
        a = FLOW_CHECKED_MOD(((a * 2)), (mod));
        b = FLOW_CHECKED_DIV((b), (2));
    }
    return result;
}

int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
    if (mod == 1) {
        return 0;
    }
    int64_t result = 1;
    int64_t b = FLOW_CHECKED_MOD((base), (mod));
    int64_t e = exp;
    while (e > 0) {
        if (FLOW_CHECKED_MOD((e), (2)) == 1) {
            result = mulmod_i64_i64_i64(result, b, mod);
        }
        b = mulmod_i64_i64_i64(b, b, mod);
        e = FLOW_CHECKED_DIV((e), (2));
    }
    return result;
}

bool is_prime_i64(int64_t n) {
    if (n < 2) {
        return 0;
    }
    if (n < 4) {
        return 1;
    }
    if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
        return 0;
    }
    int64_t i = 5;
    while ((i * i) <= n) {
        if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
            return 0;
        }
        i = (i + 6);
    }
    return 1;
}

int64_t modmul_i64_i64_i64(int64_t a, int64_t b, int64_t mod) {
    __int128 r = FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(mod))));
    if (r < ((__int128)(0))) {
        return ((int64_t)((r + ((__int128)(mod)))));
    }
    return ((int64_t)(r));
}

int64_t modadd_i64_i64_i64(int64_t a, int64_t b, int64_t mod) {
    int64_t s = (a + b);
    s = FLOW_CHECKED_MOD((s), (mod));
    if (s < 0) {
        s = (s + mod);
    }
    return s;
}

int64_t g_mod_i64_i64(int64_t n, int64_t m2) {
    int64_t mod = (6 * m2);
    int64_t n1 = FLOW_CHECKED_MOD((n), (mod));
    if (n1 < 0) {
        n1 = (n1 + mod);
    }
    int64_t n2 = modmul_i64_i64_i64(n1, n1, mod);
    int64_t n3 = modmul_i64_i64_i64(n2, n1, mod);
    int64_t num = modadd_i64_i64_i64(modadd_i64_i64_i64(n3, modmul_i64_i64_i64(5, n1, mod), mod), 6, mod);
    return FLOW_CHECKED_DIV((num), (6));
}

int64_t G_mod_i64_i64(int64_t n, int64_t m2) {
    if (n < 0) {
        return 0;
    }
    int64_t mod = (24 * m2);
    int64_t n1 = FLOW_CHECKED_MOD((n), (mod));
    int64_t n2 = modmul_i64_i64_i64(n1, n1, mod);
    int64_t n3 = modmul_i64_i64_i64(n2, n1, mod);
    int64_t n4 = modmul_i64_i64_i64(n2, n2, mod);
    int64_t num = n4;
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(2, n3, mod), mod);
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(11, n2, mod), mod);
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(34, n1, mod), mod);
    num = modadd_i64_i64_i64(num, 24, mod);
    return FLOW_CHECKED_DIV((num), (24));
}

int64_t H_mod_i64_i64(int64_t n, int64_t m2) {
    if (n < 0) {
        return 0;
    }
    int64_t mod = (24 * m2);
    int64_t n1 = FLOW_CHECKED_MOD((n), (mod));
    int64_t s1_num = modmul_i64_i64_i64(n1, (n1 + 1), (2 * mod));
    int64_t s1 = FLOW_CHECKED_DIV((FLOW_CHECKED_MOD((s1_num), ((2 * mod)))), (2));
    s1 = FLOW_CHECKED_MOD((s1), (mod));
    int64_t t2 = modmul_i64_i64_i64(modmul_i64_i64_i64(n1, (n1 + 1), (6 * mod)), FLOW_CHECKED_MOD((((2 * n1) + 1)), ((6 * mod))), (6 * mod));
    int64_t s2 = FLOW_CHECKED_DIV((t2), (6));
    s2 = FLOW_CHECKED_MOD((s2), (mod));
    int64_t s3 = modmul_i64_i64_i64(s1, s1, mod);
    int64_t u = modmul_i64_i64_i64(n1, (n1 + 1), (30 * mod));
    u = modmul_i64_i64_i64(u, FLOW_CHECKED_MOD((((2 * n1) + 1)), ((30 * mod))), (30 * mod));
    int64_t v = FLOW_CHECKED_MOD((((modmul_i64_i64_i64(3, modmul_i64_i64_i64(n1, n1, (30 * mod)), (30 * mod)) + modmul_i64_i64_i64(3, n1, (30 * mod))) - 1)), ((30 * mod)));
    if (v < 0) {
        v = (v + (30 * mod));
    }
    int64_t t4 = modmul_i64_i64_i64(u, v, (30 * mod));
    int64_t s4 = FLOW_CHECKED_DIV((t4), (30));
    s4 = FLOW_CHECKED_MOD((s4), (mod));
    int64_t num = s4;
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(2, s3, mod), mod);
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(11, s2, mod), mod);
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(34, s1, mod), mod);
    num = modadd_i64_i64_i64(num, modmul_i64_i64_i64(24, (n1 + 1), mod), mod);
    return FLOW_CHECKED_DIV((num), (24));
}

int64_t sum_G_mod_i64_i64_i64(int64_t l, int64_t r, int64_t m2) {
    if (l > r) {
        return 0;
    }
    int64_t v = (H_mod_i64_i64(r, m2) - H_mod_i64_i64((l - 1), m2));
    v = FLOW_CHECKED_MOD((v), (m2));
    if (v < 0) {
        v = (v + m2);
    }
    return v;
}

int64_t min64_i64_i64(int64_t a, int64_t b) {
    if (a < b) {
        return a;
    }
    return b;
}

int32_t main(void) {
    int64_t MOD = 100000000;
    int64_t M2 = (2 * MOD);
    int64_t N = 1000000000000;
    int64_t s = isqrt_i64(N);
    int64_t total = FLOW_CHECKED_MOD((((2 * G_mod_i64_i64(N, M2)) - 1)), (M2));
    if (total < 0) {
        total = (total + M2);
    }
    if (N >= 1) {
        int64_t f1 = FLOW_CHECKED_MOD((((G_mod_i64_i64((N + 1), M2) + G_mod_i64_i64((N - 2), M2)) - 1)), (M2));
        if (f1 < 0) {
            f1 = (f1 + M2);
        }
        total = FLOW_CHECKED_MOD(((total + (2 * f1))), (M2));
    }
    if (N >= 2) {
        int64_t fn = FLOW_CHECKED_MOD(((g_mod_i64_i64(N, M2) + g_mod_i64_i64((N + 1), M2))), (M2));
        total = FLOW_CHECKED_MOD(((total + (2 * fn))), (M2));
    }
    int64_t hi = min64_i64_i64(s, (N - 1));
    if (hi >= 2) {
        int64_t small_sum = 0;
        int64_t p = 2;
        while (p <= hi) {
            int64_t m = FLOW_CHECKED_DIV((N), (p));
            int64_t term = FLOW_CHECKED_MOD((((G_mod_i64_i64((m + p), M2) + G_mod_i64_i64((m - p), M2)) - 1)), (M2));
            if (term < 0) {
                term = (term + M2);
            }
            small_sum = FLOW_CHECKED_MOD(((small_sum + term)), (M2));
            p = (p + 1);
        }
        total = FLOW_CHECKED_MOD(((total + (2 * small_sum))), (M2));
    }
    int64_t large_sum = 0;
    int64_t m = 1;
    while (m <= s) {
        int64_t l = (FLOW_CHECKED_DIV((N), ((m + 1))) + 1);
        int64_t r = FLOW_CHECKED_DIV((N), (m));
        if (r > s) {
            if (l <= s) {
                l = (s + 1);
            }
            if (l <= r) {
                int64_t term = 0;
                if ((r == N && N >= l)) {
                    if (l <= (N - 1)) {
                        term = FLOW_CHECKED_MOD(((sum_G_mod_i64_i64_i64((l + m), ((N - 1) + m), M2) - sum_G_mod_i64_i64_i64(((l - m) - 1), (((N - 1) - m) - 1), M2))), (M2));
                    }
                } else {
                    term = FLOW_CHECKED_MOD(((sum_G_mod_i64_i64_i64((l + m), (r + m), M2) - sum_G_mod_i64_i64_i64(((l - m) - 1), ((r - m) - 1), M2))), (M2));
                }
                if (term < 0) {
                    term = (term + M2);
                }
                large_sum = FLOW_CHECKED_MOD(((large_sum + term)), (M2));
            }
        }
        m = (m + 1);
    }
    total = FLOW_CHECKED_MOD(((total + (2 * large_sum))), (M2));
    int64_t diag = ((2 * min64_i64_i64(FLOW_CHECKED_DIV((N), (2)), isqrt_i64(N))) + 1);
    total = FLOW_CHECKED_MOD(((total + FLOW_CHECKED_MOD((diag), (M2)))), (M2));
    int64_t ans = FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((total), (2))), (MOD));
    printf("%lld\n", ans);
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  func.func @gcd(%arg0: i64, %arg1: i64) -> i64 {
    %0 = llvm.mlir.constant(1 : i64) : i64
    %1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %1 : i64, !llvm.ptr
    %2 = llvm.mlir.constant(1 : i64) : i64
    %3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %3 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %4 = llvm.load %3 : !llvm.ptr -> i64
    %5 = arith.constant 0 : i32
    %7 = arith.extsi %5 : i32 to i64
    %6 = arith.cmpi ne, %4, %7 : i64
    cf.cond_br %6, ^bb1, ^bb2
    ^bb1:
      %8 = llvm.load %1 : !llvm.ptr -> i64
      %9 = llvm.load %3 : !llvm.ptr -> i64
      %10 = arith.remsi %8, %9 : i64
      %11 = llvm.load %3 : !llvm.ptr -> i64
      llvm.store %11, %1 : i64, !llvm.ptr
      llvm.store %10, %3 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %12 = llvm.load %1 : !llvm.ptr -> i64
    func.return %12 : i64
  }
  func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
    %13 = arith.constant 0 : i32
    %15 = arith.extsi %13 : i32 to i64
    %14 = arith.cmpi eq, %arg0, %15 : i64
    %16 = scf.if %14 -> (i1) {
      %17 = arith.constant true
      scf.yield %17 : i1
    } else {
      %18 = arith.constant 0 : i32
      %20 = arith.extsi %18 : i32 to i64
      %19 = arith.cmpi eq, %arg1, %20 : i64
      scf.yield %19 : i1
    }
    cf.cond_br %16, ^bb3, ^bb4
    ^bb3:
      %21 = arith.constant 0 : i32
      %22 = arith.extsi %21 : i32 to i64
      func.return %22 : i64
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
    %24 = arith.divsi %arg0, %23 : i64
    %25 = arith.muli %24, %arg1 : i64
    func.return %25 : i64
  }
  func.func @isqrt(%arg0: i64) -> i64 {
    %26 = arith.constant 2 : i32
    %28 = arith.extsi %26 : i32 to i64
    %27 = arith.cmpi slt, %arg0, %28 : i64
    cf.cond_br %27, ^bb6, ^bb7
    ^bb6:
      func.return %arg0 : i64
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %29 = llvm.mlir.constant(1 : i64) : i64
    %30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %30 : i64, !llvm.ptr
    %31 = llvm.load %30 : !llvm.ptr -> i64
    %32 = arith.constant 1 : i32
    %34 = arith.extsi %32 : i32 to i64
    %33 = arith.addi %31, %34 : i64
    %35 = arith.constant 2 : i32
    %37 = arith.extsi %35 : i32 to i64
    %36 = arith.divsi %33, %37 : i64
    %38 = llvm.mlir.constant(1 : i64) : i64
    %39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
    llvm.store %36, %39 : i64, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %40 = llvm.load %39 : !llvm.ptr -> i64
    %41 = llvm.load %30 : !llvm.ptr -> i64
    %42 = arith.cmpi slt, %40, %41 : i64
    cf.cond_br %42, ^bb10, ^bb11
    ^bb10:
      %43 = llvm.load %39 : !llvm.ptr -> i64
      llvm.store %43, %30 : i64, !llvm.ptr
      %44 = llvm.load %30 : !llvm.ptr -> i64
      %45 = llvm.load %30 : !llvm.ptr -> i64
      %46 = arith.divsi %arg0, %45 : i64
      %47 = arith.addi %44, %46 : i64
      %48 = arith.constant 2 : i32
      %50 = arith.extsi %48 : i32 to i64
      %49 = arith.divsi %47, %50 : i64
      llvm.store %49, %39 : i64, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %51 = llvm.load %30 : !llvm.ptr -> i64
    func.return %51 : i64
  }
  func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %52 = arith.remsi %arg0, %arg2 : i64
    %53 = llvm.mlir.constant(1 : i64) : i64
    %54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
    llvm.store %52, %54 : i64, !llvm.ptr
    %55 = arith.remsi %arg1, %arg2 : i64
    %56 = llvm.mlir.constant(1 : i64) : i64
    %57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
    llvm.store %55, %57 : i64, !llvm.ptr
    %58 = arith.constant 0 : i32
    %59 = arith.extsi %58 : i32 to i64
    %60 = llvm.mlir.constant(1 : i64) : i64
    %61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
    llvm.store %59, %61 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %62 = llvm.load %57 : !llvm.ptr -> i64
    %63 = arith.constant 0 : i32
    %65 = arith.extsi %63 : i32 to i64
    %64 = arith.cmpi sgt, %62, %65 : i64
    cf.cond_br %64, ^bb13, ^bb14
    ^bb13:
      %66 = llvm.load %57 : !llvm.ptr -> i64
      %67 = arith.constant 2 : i32
      %69 = arith.extsi %67 : i32 to i64
      %68 = arith.remsi %66, %69 : i64
      %70 = arith.constant 1 : i32
      %72 = arith.extsi %70 : i32 to i64
      %71 = arith.cmpi eq, %68, %72 : i64
      cf.cond_br %71, ^bb15, ^bb16
      ^bb15:
        %73 = llvm.load %61 : !llvm.ptr -> i64
        %74 = llvm.load %54 : !llvm.ptr -> i64
        %75 = arith.addi %73, %74 : i64
        %76 = arith.remsi %75, %arg2 : i64
        llvm.store %76, %61 : i64, !llvm.ptr
        cf.br ^bb17
      ^bb16:
        cf.br ^bb17
      ^bb17:
      %77 = llvm.load %54 : !llvm.ptr -> i64
      %78 = arith.constant 2 : i32
      %80 = arith.extsi %78 : i32 to i64
      %79 = arith.muli %77, %80 : i64
      %81 = arith.remsi %79, %arg2 : i64
      llvm.store %81, %54 : i64, !llvm.ptr
      %82 = llvm.load %57 : !llvm.ptr -> i64
      %83 = arith.constant 2 : i32
      %85 = arith.extsi %83 : i32 to i64
      %84 = arith.divsi %82, %85 : i64
      llvm.store %84, %57 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %86 = llvm.load %61 : !llvm.ptr -> i64
    func.return %86 : i64
  }
  func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %87 = arith.constant 1 : i32
    %89 = arith.extsi %87 : i32 to i64
    %88 = arith.cmpi eq, %arg2, %89 : i64
    cf.cond_br %88, ^bb18, ^bb19
    ^bb18:
      %90 = arith.constant 0 : i32
      %91 = arith.extsi %90 : i32 to i64
      func.return %91 : i64
    ^bb19:
      cf.br ^bb20
    ^bb20:
    %92 = arith.constant 1 : i32
    %93 = arith.extsi %92 : i32 to i64
    %94 = llvm.mlir.constant(1 : i64) : i64
    %95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
    llvm.store %93, %95 : i64, !llvm.ptr
    %96 = arith.remsi %arg0, %arg2 : i64
    %97 = llvm.mlir.constant(1 : i64) : i64
    %98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
    llvm.store %96, %98 : i64, !llvm.ptr
    %99 = llvm.mlir.constant(1 : i64) : i64
    %100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %100 : i64, !llvm.ptr
    cf.br ^bb21
    ^bb21:
    %101 = llvm.load %100 : !llvm.ptr -> i64
    %102 = arith.constant 0 : i32
    %104 = arith.extsi %102 : i32 to i64
    %103 = arith.cmpi sgt, %101, %104 : i64
    cf.cond_br %103, ^bb22, ^bb23
    ^bb22:
      %105 = llvm.load %100 : !llvm.ptr -> i64
      %106 = arith.constant 2 : i32
      %108 = arith.extsi %106 : i32 to i64
      %107 = arith.remsi %105, %108 : i64
      %109 = arith.constant 1 : i32
      %111 = arith.extsi %109 : i32 to i64
      %110 = arith.cmpi eq, %107, %111 : i64
      cf.cond_br %110, ^bb24, ^bb25
      ^bb24:
        %113 = llvm.load %95 : !llvm.ptr -> i64
        %114 = llvm.load %98 : !llvm.ptr -> i64
        %112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
        llvm.store %112, %95 : i64, !llvm.ptr
        cf.br ^bb26
      ^bb25:
        cf.br ^bb26
      ^bb26:
      %116 = llvm.load %98 : !llvm.ptr -> i64
      %117 = llvm.load %98 : !llvm.ptr -> i64
      %115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
      llvm.store %115, %98 : i64, !llvm.ptr
      %118 = llvm.load %100 : !llvm.ptr -> i64
      %119 = arith.constant 2 : i32
      %121 = arith.extsi %119 : i32 to i64
      %120 = arith.divsi %118, %121 : i64
      llvm.store %120, %100 : i64, !llvm.ptr
      cf.br ^bb21
    ^bb23:
    %122 = llvm.load %95 : !llvm.ptr -> i64
    func.return %122 : i64
  }
  func.func @is_prime(%arg0: i64) -> i1 {
    %123 = arith.constant 2 : i32
    %125 = arith.extsi %123 : i32 to i64
    %124 = arith.cmpi slt, %arg0, %125 : i64
    cf.cond_br %124, ^bb27, ^bb28
    ^bb27:
      %126 = arith.constant 0 : i1
      func.return %126 : i1
    ^bb28:
      cf.br ^bb29
    ^bb29:
    %127 = arith.constant 4 : i32
    %129 = arith.extsi %127 : i32 to i64
    %128 = arith.cmpi slt, %arg0, %129 : i64
    cf.cond_br %128, ^bb30, ^bb31
    ^bb30:
      %130 = arith.constant 1 : i1
      func.return %130 : i1
    ^bb31:
      cf.br ^bb32
    ^bb32:
    %131 = arith.constant 2 : i32
    %133 = arith.extsi %131 : i32 to i64
    %132 = arith.remsi %arg0, %133 : i64
    %134 = arith.constant 0 : i32
    %136 = arith.extsi %134 : i32 to i64
    %135 = arith.cmpi eq, %132, %136 : i64
    %137 = scf.if %135 -> (i1) {
      %138 = arith.constant true
      scf.yield %138 : i1
    } else {
      %139 = arith.constant 3 : i32
      %141 = arith.extsi %139 : i32 to i64
      %140 = arith.remsi %arg0, %141 : i64
      %142 = arith.constant 0 : i32
      %144 = arith.extsi %142 : i32 to i64
      %143 = arith.cmpi eq, %140, %144 : i64
      scf.yield %143 : i1
    }
    cf.cond_br %137, ^bb33, ^bb34
    ^bb33:
      %145 = arith.constant 0 : i1
      func.return %145 : i1
    ^bb34:
      cf.br ^bb35
    ^bb35:
    %146 = arith.constant 5 : i32
    %147 = arith.extsi %146 : i32 to i64
    %148 = llvm.mlir.constant(1 : i64) : i64
    %149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
    llvm.store %147, %149 : i64, !llvm.ptr
    cf.br ^bb36
    ^bb36:
    %150 = llvm.load %149 : !llvm.ptr -> i64
    %151 = llvm.load %149 : !llvm.ptr -> i64
    %152 = arith.muli %150, %151 : i64
    %153 = arith.cmpi sle, %152, %arg0 : i64
    cf.cond_br %153, ^bb37, ^bb38
    ^bb37:
      %154 = llvm.load %149 : !llvm.ptr -> i64
      %155 = arith.remsi %arg0, %154 : i64
      %156 = arith.constant 0 : i32
      %158 = arith.extsi %156 : i32 to i64
      %157 = arith.cmpi eq, %155, %158 : i64
      %159 = scf.if %157 -> (i1) {
        %160 = arith.constant true
        scf.yield %160 : i1
      } else {
        %161 = llvm.load %149 : !llvm.ptr -> i64
        %162 = arith.constant 2 : i32
        %164 = arith.extsi %162 : i32 to i64
        %163 = arith.addi %161, %164 : i64
        %165 = arith.remsi %arg0, %163 : i64
        %166 = arith.constant 0 : i32
        %168 = arith.extsi %166 : i32 to i64
        %167 = arith.cmpi eq, %165, %168 : i64
        scf.yield %167 : i1
      }
      cf.cond_br %159, ^bb39, ^bb40
      ^bb39:
        %169 = arith.constant 0 : i1
        func.return %169 : i1
      ^bb40:
        cf.br ^bb41
      ^bb41:
      %170 = llvm.load %149 : !llvm.ptr -> i64
      %171 = arith.constant 6 : i32
      %173 = arith.extsi %171 : i32 to i64
      %172 = arith.addi %170, %173 : i64
      llvm.store %172, %149 : i64, !llvm.ptr
      cf.br ^bb36
    ^bb38:
    %174 = arith.constant 1 : i1
    func.return %174 : i1
  }
  func.func @modmul(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %175 = arith.extsi %arg0 : i64 to i128
    %176 = arith.extsi %arg1 : i64 to i128
    %178 = arith.trunci %175 : i128 to i64
    %179 = arith.trunci %176 : i128 to i64
    %177 = arith.muli %178, %179 : i64
    %180 = arith.extsi %arg2 : i64 to i128
    %182 = arith.trunci %180 : i128 to i64
    %181 = arith.remsi %177, %182 : i64
    %183 = arith.extsi %181 : i64 to i128
    %184 = arith.constant 0 : i32
    %185 = arith.extsi %184 : i32 to i128
    %187 = arith.trunci %183 : i128 to i64
    %188 = arith.trunci %185 : i128 to i64
    %186 = arith.cmpi slt, %187, %188 : i64
    cf.cond_br %186, ^bb42, ^bb43
    ^bb42:
      %189 = arith.extsi %arg2 : i64 to i128
      %191 = arith.trunci %183 : i128 to i64
      %192 = arith.trunci %189 : i128 to i64
      %190 = arith.addi %191, %192 : i64
      func.return %190 : i64
    ^bb43:
      cf.br ^bb44
    ^bb44:
    %193 = arith.trunci %183 : i128 to i64
    func.return %193 : i64
  }
  func.func @modadd(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %194 = arith.addi %arg0, %arg1 : i64
    %195 = llvm.mlir.constant(1 : i64) : i64
    %196 = llvm.alloca %195 x i64 : (i64) -> !llvm.ptr
    llvm.store %194, %196 : i64, !llvm.ptr
    %197 = llvm.load %196 : !llvm.ptr -> i64
    %198 = arith.remsi %197, %arg2 : i64
    llvm.store %198, %196 : i64, !llvm.ptr
    %199 = llvm.load %196 : !llvm.ptr -> i64
    %200 = arith.constant 0 : i32
    %202 = arith.extsi %200 : i32 to i64
    %201 = arith.cmpi slt, %199, %202 : i64
    cf.cond_br %201, ^bb45, ^bb46
    ^bb45:
      %203 = llvm.load %196 : !llvm.ptr -> i64
      %204 = arith.addi %203, %arg2 : i64
      llvm.store %204, %196 : i64, !llvm.ptr
      cf.br ^bb47
    ^bb46:
      cf.br ^bb47
    ^bb47:
    %205 = llvm.load %196 : !llvm.ptr -> i64
    func.return %205 : i64
  }
  func.func @g_mod(%arg0: i64, %arg1: i64) -> i64 {
    %206 = arith.constant 6 : i32
    %208 = arith.extsi %206 : i32 to i64
    %207 = arith.muli %208, %arg1 : i64
    %209 = arith.remsi %arg0, %207 : i64
    %210 = arith.constant 0 : i32
    %212 = arith.extsi %210 : i32 to i64
    %211 = arith.cmpi slt, %209, %212 : i64
    %213 = scf.if %211 -> (i64) {
      %214 = arith.addi %209, %207 : i64
      scf.yield %214 : i64
    } else {
      scf.yield %209 : i64
    }
    %215 = func.call @modmul(%213, %213, %207) : (i64, i64, i64) -> i64
    %216 = func.call @modmul(%215, %213, %207) : (i64, i64, i64) -> i64
    %220 = arith.constant 5 : i32
    %221 = arith.extsi %220 : i32 to i64
    %219 = func.call @modmul(%221, %213, %207) : (i64, i64, i64) -> i64
    %218 = func.call @modadd(%216, %219, %207) : (i64, i64, i64) -> i64
    %222 = arith.constant 6 : i32
    %223 = arith.extsi %222 : i32 to i64
    %217 = func.call @modadd(%218, %223, %207) : (i64, i64, i64) -> i64
    %224 = arith.constant 6 : i32
    %226 = arith.extsi %224 : i32 to i64
    %225 = arith.divsi %217, %226 : i64
    func.return %225 : i64
  }
  func.func @G_mod(%arg0: i64, %arg1: i64) -> i64 {
    %227 = arith.constant 0 : i32
    %229 = arith.extsi %227 : i32 to i64
    %228 = arith.cmpi slt, %arg0, %229 : i64
    cf.cond_br %228, ^bb48, ^bb49
    ^bb48:
      %230 = arith.constant 0 : i32
      %231 = arith.extsi %230 : i32 to i64
      func.return %231 : i64
    ^bb49:
      cf.br ^bb50
    ^bb50:
    %232 = arith.constant 24 : i32
    %234 = arith.extsi %232 : i32 to i64
    %233 = arith.muli %234, %arg1 : i64
    %235 = arith.remsi %arg0, %233 : i64
    %236 = func.call @modmul(%235, %235, %233) : (i64, i64, i64) -> i64
    %237 = func.call @modmul(%236, %235, %233) : (i64, i64, i64) -> i64
    %238 = func.call @modmul(%236, %236, %233) : (i64, i64, i64) -> i64
    %239 = llvm.mlir.constant(1 : i64) : i64
    %240 = llvm.alloca %239 x i64 : (i64) -> !llvm.ptr
    llvm.store %238, %240 : i64, !llvm.ptr
    %242 = llvm.load %240 : !llvm.ptr -> i64
    %244 = arith.constant 2 : i32
    %245 = arith.extsi %244 : i32 to i64
    %243 = func.call @modmul(%245, %237, %233) : (i64, i64, i64) -> i64
    %241 = func.call @modadd(%242, %243, %233) : (i64, i64, i64) -> i64
    llvm.store %241, %240 : i64, !llvm.ptr
    %247 = llvm.load %240 : !llvm.ptr -> i64
    %249 = arith.constant 11 : i32
    %250 = arith.extsi %249 : i32 to i64
    %248 = func.call @modmul(%250, %236, %233) : (i64, i64, i64) -> i64
    %246 = func.call @modadd(%247, %248, %233) : (i64, i64, i64) -> i64
    llvm.store %246, %240 : i64, !llvm.ptr
    %252 = llvm.load %240 : !llvm.ptr -> i64
    %254 = arith.constant 34 : i32
    %255 = arith.extsi %254 : i32 to i64
    %253 = func.call @modmul(%255, %235, %233) : (i64, i64, i64) -> i64
    %251 = func.call @modadd(%252, %253, %233) : (i64, i64, i64) -> i64
    llvm.store %251, %240 : i64, !llvm.ptr
    %257 = llvm.load %240 : !llvm.ptr -> i64
    %258 = arith.constant 24 : i32
    %259 = arith.extsi %258 : i32 to i64
    %256 = func.call @modadd(%257, %259, %233) : (i64, i64, i64) -> i64
    llvm.store %256, %240 : i64, !llvm.ptr
    %260 = llvm.load %240 : !llvm.ptr -> i64
    %261 = arith.constant 24 : i32
    %263 = arith.extsi %261 : i32 to i64
    %262 = arith.divsi %260, %263 : i64
    func.return %262 : i64
  }
  func.func @H_mod(%arg0: i64, %arg1: i64) -> i64 {
    %264 = arith.constant 0 : i32
    %266 = arith.extsi %264 : i32 to i64
    %265 = arith.cmpi slt, %arg0, %266 : i64
    cf.cond_br %265, ^bb51, ^bb52
    ^bb51:
      %267 = arith.constant 0 : i32
      %268 = arith.extsi %267 : i32 to i64
      func.return %268 : i64
    ^bb52:
      cf.br ^bb53
    ^bb53:
    %269 = arith.constant 24 : i32
    %271 = arith.extsi %269 : i32 to i64
    %270 = arith.muli %271, %arg1 : i64
    %272 = arith.remsi %arg0, %270 : i64
    %274 = arith.constant 1 : i32
    %276 = arith.extsi %274 : i32 to i64
    %275 = arith.addi %272, %276 : i64
    %277 = arith.constant 2 : i32
    %279 = arith.extsi %277 : i32 to i64
    %278 = arith.muli %279, %270 : i64
    %273 = func.call @modmul(%272, %275, %278) : (i64, i64, i64) -> i64
    %280 = arith.constant 2 : i32
    %282 = arith.extsi %280 : i32 to i64
    %281 = arith.muli %282, %270 : i64
    %283 = arith.remsi %273, %281 : i64
    %284 = arith.constant 2 : i32
    %286 = arith.extsi %284 : i32 to i64
    %285 = arith.divsi %283, %286 : i64
    %287 = arith.remsi %285, %270 : i64
    %290 = arith.constant 1 : i32
    %292 = arith.extsi %290 : i32 to i64
    %291 = arith.addi %272, %292 : i64
    %293 = arith.constant 6 : i32
    %295 = arith.extsi %293 : i32 to i64
    %294 = arith.muli %295, %270 : i64
    %289 = func.call @modmul(%272, %291, %294) : (i64, i64, i64) -> i64
    %296 = arith.constant 2 : i32
    %298 = arith.extsi %296 : i32 to i64
    %297 = arith.muli %298, %272 : i64
    %299 = arith.constant 1 : i32
    %301 = arith.extsi %299 : i32 to i64
    %300 = arith.addi %297, %301 : i64
    %302 = arith.constant 6 : i32
    %304 = arith.extsi %302 : i32 to i64
    %303 = arith.muli %304, %270 : i64
    %305 = arith.remsi %300, %303 : i64
    %306 = arith.constant 6 : i32
    %308 = arith.extsi %306 : i32 to i64
    %307 = arith.muli %308, %270 : i64
    %288 = func.call @modmul(%289, %305, %307) : (i64, i64, i64) -> i64
    %309 = arith.constant 6 : i32
    %311 = arith.extsi %309 : i32 to i64
    %310 = arith.divsi %288, %311 : i64
    %312 = arith.remsi %310, %270 : i64
    %313 = func.call @modmul(%287, %287, %270) : (i64, i64, i64) -> i64
    %315 = arith.constant 1 : i32
    %317 = arith.extsi %315 : i32 to i64
    %316 = arith.addi %272, %317 : i64
    %318 = arith.constant 30 : i32
    %320 = arith.extsi %318 : i32 to i64
    %319 = arith.muli %320, %270 : i64
    %314 = func.call @modmul(%272, %316, %319) : (i64, i64, i64) -> i64
    %322 = arith.constant 2 : i32
    %324 = arith.extsi %322 : i32 to i64
    %323 = arith.muli %324, %272 : i64
    %325 = arith.constant 1 : i32
    %327 = arith.extsi %325 : i32 to i64
    %326 = arith.addi %323, %327 : i64
    %328 = arith.constant 30 : i32
    %330 = arith.extsi %328 : i32 to i64
    %329 = arith.muli %330, %270 : i64
    %331 = arith.remsi %326, %329 : i64
    %332 = arith.constant 30 : i32
    %334 = arith.extsi %332 : i32 to i64
    %333 = arith.muli %334, %270 : i64
    %321 = func.call @modmul(%314, %331, %333) : (i64, i64, i64) -> i64
    %336 = arith.constant 3 : i32
    %338 = arith.constant 30 : i32
    %340 = arith.extsi %338 : i32 to i64
    %339 = arith.muli %340, %270 : i64
    %337 = func.call @modmul(%272, %272, %339) : (i64, i64, i64) -> i64
    %341 = arith.constant 30 : i32
    %343 = arith.extsi %341 : i32 to i64
    %342 = arith.muli %343, %270 : i64
    %344 = arith.extsi %336 : i32 to i64
    %335 = func.call @modmul(%344, %337, %342) : (i64, i64, i64) -> i64
    %346 = arith.constant 3 : i32
    %347 = arith.constant 30 : i32
    %349 = arith.extsi %347 : i32 to i64
    %348 = arith.muli %349, %270 : i64
    %350 = arith.extsi %346 : i32 to i64
    %345 = func.call @modmul(%350, %272, %348) : (i64, i64, i64) -> i64
    %351 = arith.addi %335, %345 : i64
    %352 = arith.constant 1 : i32
    %354 = arith.extsi %352 : i32 to i64
    %353 = arith.subi %351, %354 : i64
    %355 = arith.constant 30 : i32
    %357 = arith.extsi %355 : i32 to i64
    %356 = arith.muli %357, %270 : i64
    %358 = arith.remsi %353, %356 : i64
    %359 = arith.constant 0 : i32
    %361 = arith.extsi %359 : i32 to i64
    %360 = arith.cmpi slt, %358, %361 : i64
    %362 = scf.if %360 -> (i64) {
      %363 = arith.constant 30 : i32
      %365 = arith.extsi %363 : i32 to i64
      %364 = arith.muli %365, %270 : i64
      %366 = arith.addi %358, %364 : i64
      scf.yield %366 : i64
    } else {
      scf.yield %358 : i64
    }
    %368 = arith.constant 30 : i32
    %370 = arith.extsi %368 : i32 to i64
    %369 = arith.muli %370, %270 : i64
    %367 = func.call @modmul(%321, %362, %369) : (i64, i64, i64) -> i64
    %371 = arith.constant 30 : i32
    %373 = arith.extsi %371 : i32 to i64
    %372 = arith.divsi %367, %373 : i64
    %374 = arith.remsi %372, %270 : i64
    %375 = llvm.mlir.constant(1 : i64) : i64
    %376 = llvm.alloca %375 x i64 : (i64) -> !llvm.ptr
    llvm.store %374, %376 : i64, !llvm.ptr
    %378 = llvm.load %376 : !llvm.ptr -> i64
    %380 = arith.constant 2 : i32
    %381 = arith.extsi %380 : i32 to i64
    %379 = func.call @modmul(%381, %313, %270) : (i64, i64, i64) -> i64
    %377 = func.call @modadd(%378, %379, %270) : (i64, i64, i64) -> i64
    llvm.store %377, %376 : i64, !llvm.ptr
    %383 = llvm.load %376 : !llvm.ptr -> i64
    %385 = arith.constant 11 : i32
    %386 = arith.extsi %385 : i32 to i64
    %384 = func.call @modmul(%386, %312, %270) : (i64, i64, i64) -> i64
    %382 = func.call @modadd(%383, %384, %270) : (i64, i64, i64) -> i64
    llvm.store %382, %376 : i64, !llvm.ptr
    %388 = llvm.load %376 : !llvm.ptr -> i64
    %390 = arith.constant 34 : i32
    %391 = arith.extsi %390 : i32 to i64
    %389 = func.call @modmul(%391, %287, %270) : (i64, i64, i64) -> i64
    %387 = func.call @modadd(%388, %389, %270) : (i64, i64, i64) -> i64
    llvm.store %387, %376 : i64, !llvm.ptr
    %393 = llvm.load %376 : !llvm.ptr -> i64
    %395 = arith.constant 24 : i32
    %396 = arith.constant 1 : i32
    %398 = arith.extsi %396 : i32 to i64
    %397 = arith.addi %272, %398 : i64
    %399 = arith.extsi %395 : i32 to i64
    %394 = func.call @modmul(%399, %397, %270) : (i64, i64, i64) -> i64
    %392 = func.call @modadd(%393, %394, %270) : (i64, i64, i64) -> i64
    llvm.store %392, %376 : i64, !llvm.ptr
    %400 = llvm.load %376 : !llvm.ptr -> i64
    %401 = arith.constant 24 : i32
    %403 = arith.extsi %401 : i32 to i64
    %402 = arith.divsi %400, %403 : i64
    func.return %402 : i64
  }
  func.func @sum_G_mod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %404 = arith.cmpi sgt, %arg0, %arg1 : i64
    cf.cond_br %404, ^bb54, ^bb55
    ^bb54:
      %405 = arith.constant 0 : i32
      %406 = arith.extsi %405 : i32 to i64
      func.return %406 : i64
    ^bb55:
      cf.br ^bb56
    ^bb56:
    %407 = func.call @H_mod(%arg1, %arg2) : (i64, i64) -> i64
    %409 = arith.constant 1 : i32
    %411 = arith.extsi %409 : i32 to i64
    %410 = arith.subi %arg0, %411 : i64
    %408 = func.call @H_mod(%410, %arg2) : (i64, i64) -> i64
    %412 = arith.subi %407, %408 : i64
    %413 = llvm.mlir.constant(1 : i64) : i64
    %414 = llvm.alloca %413 x i64 : (i64) -> !llvm.ptr
    llvm.store %412, %414 : i64, !llvm.ptr
    %415 = llvm.load %414 : !llvm.ptr -> i64
    %416 = arith.remsi %415, %arg2 : i64
    llvm.store %416, %414 : i64, !llvm.ptr
    %417 = llvm.load %414 : !llvm.ptr -> i64
    %418 = arith.constant 0 : i32
    %420 = arith.extsi %418 : i32 to i64
    %419 = arith.cmpi slt, %417, %420 : i64
    cf.cond_br %419, ^bb57, ^bb58
    ^bb57:
      %421 = llvm.load %414 : !llvm.ptr -> i64
      %422 = arith.addi %421, %arg2 : i64
      llvm.store %422, %414 : i64, !llvm.ptr
      cf.br ^bb59
    ^bb58:
      cf.br ^bb59
    ^bb59:
    %423 = llvm.load %414 : !llvm.ptr -> i64
    func.return %423 : i64
  }
  func.func @min64(%arg0: i64, %arg1: i64) -> i64 {
    %424 = arith.cmpi slt, %arg0, %arg1 : i64
    cf.cond_br %424, ^bb60, ^bb61
    ^bb60:
      func.return %arg0 : i64
    ^bb61:
      cf.br ^bb62
    ^bb62:
    func.return %arg1 : i64
  }
  func.func @main() -> i32 {
    %425 = arith.constant 100000000 : i32
    %426 = arith.extsi %425 : i32 to i64
    %427 = arith.constant 2 : i32
    %429 = arith.extsi %427 : i32 to i64
    %428 = arith.muli %429, %426 : i64
    %430 = arith.constant 995705032704 : i32
    %431 = arith.extsi %430 : i32 to i64
    %432 = func.call @isqrt(%431) : (i64) -> i64
    %433 = arith.constant 2 : i32
    %434 = func.call @G_mod(%431, %428) : (i64, i64) -> i64
    %436 = arith.extsi %433 : i32 to i64
    %435 = arith.muli %436, %434 : i64
    %437 = arith.constant 1 : i32
    %439 = arith.extsi %437 : i32 to i64
    %438 = arith.subi %435, %439 : i64
    %440 = arith.remsi %438, %428 : i64
    %441 = llvm.mlir.constant(1 : i64) : i64
    %442 = llvm.alloca %441 x i64 : (i64) -> !llvm.ptr
    llvm.store %440, %442 : i64, !llvm.ptr
    %443 = llvm.load %442 : !llvm.ptr -> i64
    %444 = arith.constant 0 : i32
    %446 = arith.extsi %444 : i32 to i64
    %445 = arith.cmpi slt, %443, %446 : i64
    cf.cond_br %445, ^bb63, ^bb64
    ^bb63:
      %447 = llvm.load %442 : !llvm.ptr -> i64
      %448 = arith.addi %447, %428 : i64
      llvm.store %448, %442 : i64, !llvm.ptr
      cf.br ^bb65
    ^bb64:
      cf.br ^bb65
    ^bb65:
    %449 = arith.constant 1 : i32
    %451 = arith.extsi %449 : i32 to i64
    %450 = arith.cmpi sge, %431, %451 : i64
    cf.cond_br %450, ^bb66, ^bb67
    ^bb66:
      %453 = arith.constant 1 : i32
      %455 = arith.extsi %453 : i32 to i64
      %454 = arith.addi %431, %455 : i64
      %452 = func.call @G_mod(%454, %428) : (i64, i64) -> i64
      %457 = arith.constant 2 : i32
      %459 = arith.extsi %457 : i32 to i64
      %458 = arith.subi %431, %459 : i64
      %456 = func.call @G_mod(%458, %428) : (i64, i64) -> i64
      %460 = arith.addi %452, %456 : i64
      %461 = arith.constant 1 : i32
      %463 = arith.extsi %461 : i32 to i64
      %462 = arith.subi %460, %463 : i64
      %464 = arith.remsi %462, %428 : i64
      %465 = arith.constant 0 : i32
      %467 = arith.extsi %465 : i32 to i64
      %466 = arith.cmpi slt, %464, %467 : i64
      %468 = scf.if %466 -> (i64) {
        %469 = arith.addi %464, %428 : i64
        scf.yield %469 : i64
      } else {
        scf.yield %464 : i64
      }
      %470 = llvm.load %442 : !llvm.ptr -> i64
      %471 = arith.constant 2 : i32
      %473 = arith.extsi %471 : i32 to i64
      %472 = arith.muli %473, %468 : i64
      %474 = arith.addi %470, %472 : i64
      %475 = arith.remsi %474, %428 : i64
      llvm.store %475, %442 : i64, !llvm.ptr
      cf.br ^bb68
    ^bb67:
      cf.br ^bb68
    ^bb68:
    %476 = arith.constant 2 : i32
    %478 = arith.extsi %476 : i32 to i64
    %477 = arith.cmpi sge, %431, %478 : i64
    cf.cond_br %477, ^bb69, ^bb70
    ^bb69:
      %479 = func.call @g_mod(%431, %428) : (i64, i64) -> i64
      %481 = arith.constant 1 : i32
      %483 = arith.extsi %481 : i32 to i64
      %482 = arith.addi %431, %483 : i64
      %480 = func.call @g_mod(%482, %428) : (i64, i64) -> i64
      %484 = arith.addi %479, %480 : i64
      %485 = arith.remsi %484, %428 : i64
      %486 = llvm.load %442 : !llvm.ptr -> i64
      %487 = arith.constant 2 : i32
      %489 = arith.extsi %487 : i32 to i64
      %488 = arith.muli %489, %485 : i64
      %490 = arith.addi %486, %488 : i64
      %491 = arith.remsi %490, %428 : i64
      llvm.store %491, %442 : i64, !llvm.ptr
      cf.br ^bb71
    ^bb70:
      cf.br ^bb71
    ^bb71:
    %493 = arith.constant 1 : i32
    %495 = arith.extsi %493 : i32 to i64
    %494 = arith.subi %431, %495 : i64
    %492 = func.call @min64(%432, %494) : (i64, i64) -> i64
    %496 = arith.constant 2 : i32
    %498 = arith.extsi %496 : i32 to i64
    %497 = arith.cmpi sge, %492, %498 : i64
    cf.cond_br %497, ^bb72, ^bb73
    ^bb72:
      %499 = arith.constant 0 : i32
      %500 = arith.extsi %499 : i32 to i64
      %501 = llvm.mlir.constant(1 : i64) : i64
      %502 = llvm.alloca %501 x i64 : (i64) -> !llvm.ptr
      llvm.store %500, %502 : i64, !llvm.ptr
      %503 = arith.constant 2 : i32
      %504 = arith.extsi %503 : i32 to i64
      %505 = llvm.mlir.constant(1 : i64) : i64
      %506 = llvm.alloca %505 x i64 : (i64) -> !llvm.ptr
      llvm.store %504, %506 : i64, !llvm.ptr
      cf.br ^bb75
      ^bb75:
      %507 = llvm.load %506 : !llvm.ptr -> i64
      %508 = arith.cmpi sle, %507, %492 : i64
      cf.cond_br %508, ^bb76, ^bb77
      ^bb76:
        %509 = llvm.load %506 : !llvm.ptr -> i64
        %510 = arith.divsi %431, %509 : i64
        %512 = llvm.load %506 : !llvm.ptr -> i64
        %513 = arith.addi %510, %512 : i64
        %511 = func.call @G_mod(%513, %428) : (i64, i64) -> i64
        %515 = llvm.load %506 : !llvm.ptr -> i64
        %516 = arith.subi %510, %515 : i64
        %514 = func.call @G_mod(%516, %428) : (i64, i64) -> i64
        %517 = arith.addi %511, %514 : i64
        %518 = arith.constant 1 : i32
        %520 = arith.extsi %518 : i32 to i64
        %519 = arith.subi %517, %520 : i64
        %521 = arith.remsi %519, %428 : i64
        %522 = arith.constant 0 : i32
        %524 = arith.extsi %522 : i32 to i64
        %523 = arith.cmpi slt, %521, %524 : i64
        %525 = scf.if %523 -> (i64) {
          %526 = arith.addi %521, %428 : i64
          scf.yield %526 : i64
        } else {
          scf.yield %521 : i64
        }
        %527 = llvm.load %502 : !llvm.ptr -> i64
        %528 = arith.addi %527, %525 : i64
        %529 = arith.remsi %528, %428 : i64
        llvm.store %529, %502 : i64, !llvm.ptr
        %530 = llvm.load %506 : !llvm.ptr -> i64
        %531 = arith.constant 1 : i32
        %533 = arith.extsi %531 : i32 to i64
        %532 = arith.addi %530, %533 : i64
        llvm.store %532, %506 : i64, !llvm.ptr
        cf.br ^bb75
      ^bb77:
      %534 = llvm.load %442 : !llvm.ptr -> i64
      %535 = arith.constant 2 : i32
      %536 = llvm.load %502 : !llvm.ptr -> i64
      %538 = arith.extsi %535 : i32 to i64
      %537 = arith.muli %538, %536 : i64
      %539 = arith.addi %534, %537 : i64
      %540 = arith.remsi %539, %428 : i64
      llvm.store %540, %442 : i64, !llvm.ptr
      cf.br ^bb74
    ^bb73:
      cf.br ^bb74
    ^bb74:
    %541 = arith.constant 0 : i32
    %542 = arith.extsi %541 : i32 to i64
    %543 = llvm.mlir.constant(1 : i64) : i64
    %544 = llvm.alloca %543 x i64 : (i64) -> !llvm.ptr
    llvm.store %542, %544 : i64, !llvm.ptr
    %545 = arith.constant 1 : i32
    %546 = arith.extsi %545 : i32 to i64
    %547 = llvm.mlir.constant(1 : i64) : i64
    %548 = llvm.alloca %547 x i64 : (i64) -> !llvm.ptr
    llvm.store %546, %548 : i64, !llvm.ptr
    cf.br ^bb78
    ^bb78:
    %549 = llvm.load %548 : !llvm.ptr -> i64
    %550 = arith.cmpi sle, %549, %432 : i64
    cf.cond_br %550, ^bb79, ^bb80
    ^bb79:
      %551 = llvm.load %548 : !llvm.ptr -> i64
      %552 = arith.constant 1 : i32
      %554 = arith.extsi %552 : i32 to i64
      %553 = arith.addi %551, %554 : i64
      %555 = arith.divsi %431, %553 : i64
      %556 = arith.constant 1 : i32
      %558 = arith.extsi %556 : i32 to i64
      %557 = arith.addi %555, %558 : i64
      %559 = llvm.mlir.constant(1 : i64) : i64
      %560 = llvm.alloca %559 x i64 : (i64) -> !llvm.ptr
      llvm.store %557, %560 : i64, !llvm.ptr
      %561 = llvm.load %548 : !llvm.ptr -> i64
      %562 = arith.divsi %431, %561 : i64
      %563 = arith.cmpi sgt, %562, %432 : i64
      cf.cond_br %563, ^bb81, ^bb82
      ^bb81:
        %564 = llvm.load %560 : !llvm.ptr -> i64
        %565 = arith.cmpi sle, %564, %432 : i64
        cf.cond_br %565, ^bb84, ^bb85
        ^bb84:
          %566 = arith.constant 1 : i32
          %568 = arith.extsi %566 : i32 to i64
          %567 = arith.addi %432, %568 : i64
          llvm.store %567, %560 : i64, !llvm.ptr
          cf.br ^bb86
        ^bb85:
          cf.br ^bb86
        ^bb86:
        %569 = llvm.load %560 : !llvm.ptr -> i64
        %570 = arith.cmpi sle, %569, %562 : i64
        cf.cond_br %570, ^bb87, ^bb88
        ^bb87:
          %571 = arith.constant 0 : i32
          %572 = arith.extsi %571 : i32 to i64
          %573 = llvm.mlir.constant(1 : i64) : i64
          %574 = llvm.alloca %573 x i64 : (i64) -> !llvm.ptr
          llvm.store %572, %574 : i64, !llvm.ptr
          %575 = arith.cmpi eq, %562, %431 : i64
          %576 = scf.if %575 -> (i1) {
            %577 = llvm.load %560 : !llvm.ptr -> i64
            %578 = arith.cmpi sge, %431, %577 : i64
            scf.yield %578 : i1
          } else {
            %579 = arith.constant false
            scf.yield %579 : i1
          }
          cf.cond_br %576, ^bb90, ^bb91
          ^bb90:
            %580 = llvm.load %560 : !llvm.ptr -> i64
            %581 = arith.constant 1 : i32
            %583 = arith.extsi %581 : i32 to i64
            %582 = arith.subi %431, %583 : i64
            %584 = arith.cmpi sle, %580, %582 : i64
            cf.cond_br %584, ^bb93, ^bb94
            ^bb93:
              %586 = llvm.load %560 : !llvm.ptr -> i64
              %587 = llvm.load %548 : !llvm.ptr -> i64
              %588 = arith.addi %586, %587 : i64
              %589 = arith.constant 1 : i32
              %591 = arith.extsi %589 : i32 to i64
              %590 = arith.subi %431, %591 : i64
              %592 = llvm.load %548 : !llvm.ptr -> i64
              %593 = arith.addi %590, %592 : i64
              %585 = func.call @sum_G_mod(%588, %593, %428) : (i64, i64, i64) -> i64
              %595 = llvm.load %560 : !llvm.ptr -> i64
              %596 = llvm.load %548 : !llvm.ptr -> i64
              %597 = arith.subi %595, %596 : i64
              %598 = arith.constant 1 : i32
              %600 = arith.extsi %598 : i32 to i64
              %599 = arith.subi %597, %600 : i64
              %601 = arith.constant 1 : i32
              %603 = arith.extsi %601 : i32 to i64
              %602 = arith.subi %431, %603 : i64
              %604 = llvm.load %548 : !llvm.ptr -> i64
              %605 = arith.subi %602, %604 : i64
              %606 = arith.constant 1 : i32
              %608 = arith.extsi %606 : i32 to i64
              %607 = arith.subi %605, %608 : i64
              %594 = func.call @sum_G_mod(%599, %607, %428) : (i64, i64, i64) -> i64
              %609 = arith.subi %585, %594 : i64
              %610 = arith.remsi %609, %428 : i64
              llvm.store %610, %574 : i64, !llvm.ptr
              cf.br ^bb95
            ^bb94:
              cf.br ^bb95
            ^bb95:
            cf.br ^bb92
          ^bb91:
            %612 = llvm.load %560 : !llvm.ptr -> i64
            %613 = llvm.load %548 : !llvm.ptr -> i64
            %614 = arith.addi %612, %613 : i64
            %615 = llvm.load %548 : !llvm.ptr -> i64
            %616 = arith.addi %562, %615 : i64
            %611 = func.call @sum_G_mod(%614, %616, %428) : (i64, i64, i64) -> i64
            %618 = llvm.load %560 : !llvm.ptr -> i64
            %619 = llvm.load %548 : !llvm.ptr -> i64
            %620 = arith.subi %618, %619 : i64
            %621 = arith.constant 1 : i32
            %623 = arith.extsi %621 : i32 to i64
            %622 = arith.subi %620, %623 : i64
            %624 = llvm.load %548 : !llvm.ptr -> i64
            %625 = arith.subi %562, %624 : i64
            %626 = arith.constant 1 : i32
            %628 = arith.extsi %626 : i32 to i64
            %627 = arith.subi %625, %628 : i64
            %617 = func.call @sum_G_mod(%622, %627, %428) : (i64, i64, i64) -> i64
            %629 = arith.subi %611, %617 : i64
            %630 = arith.remsi %629, %428 : i64
            llvm.store %630, %574 : i64, !llvm.ptr
            cf.br ^bb92
          ^bb92:
          %631 = llvm.load %574 : !llvm.ptr -> i64
          %632 = arith.constant 0 : i32
          %634 = arith.extsi %632 : i32 to i64
          %633 = arith.cmpi slt, %631, %634 : i64
          cf.cond_br %633, ^bb96, ^bb97
          ^bb96:
            %635 = llvm.load %574 : !llvm.ptr -> i64
            %636 = arith.addi %635, %428 : i64
            llvm.store %636, %574 : i64, !llvm.ptr
            cf.br ^bb98
          ^bb97:
            cf.br ^bb98
          ^bb98:
          %637 = llvm.load %544 : !llvm.ptr -> i64
          %638 = llvm.load %574 : !llvm.ptr -> i64
          %639 = arith.addi %637, %638 : i64
          %640 = arith.remsi %639, %428 : i64
          llvm.store %640, %544 : i64, !llvm.ptr
          cf.br ^bb89
        ^bb88:
          cf.br ^bb89
        ^bb89:
        cf.br ^bb83
      ^bb82:
        cf.br ^bb83
      ^bb83:
      %641 = llvm.load %548 : !llvm.ptr -> i64
      %642 = arith.constant 1 : i32
      %644 = arith.extsi %642 : i32 to i64
      %643 = arith.addi %641, %644 : i64
      llvm.store %643, %548 : i64, !llvm.ptr
      cf.br ^bb78
    ^bb80:
    %645 = llvm.load %442 : !llvm.ptr -> i64
    %646 = arith.constant 2 : i32
    %647 = llvm.load %544 : !llvm.ptr -> i64
    %649 = arith.extsi %646 : i32 to i64
    %648 = arith.muli %649, %647 : i64
    %650 = arith.addi %645, %648 : i64
    %651 = arith.remsi %650, %428 : i64
    llvm.store %651, %442 : i64, !llvm.ptr
    %652 = arith.constant 2 : i32
    %654 = arith.constant 2 : i32
    %656 = arith.extsi %654 : i32 to i64
    %655 = arith.divsi %431, %656 : i64
    %657 = func.call @isqrt(%431) : (i64) -> i64
    %653 = func.call @min64(%655, %657) : (i64, i64) -> i64
    %659 = arith.extsi %652 : i32 to i64
    %658 = arith.muli %659, %653 : i64
    %660 = arith.constant 1 : i32
    %662 = arith.extsi %660 : i32 to i64
    %661 = arith.addi %658, %662 : i64
    %663 = llvm.load %442 : !llvm.ptr -> i64
    %664 = arith.remsi %661, %428 : i64
    %665 = arith.addi %663, %664 : i64
    %666 = arith.remsi %665, %428 : i64
    llvm.store %666, %442 : i64, !llvm.ptr
    %667 = llvm.load %442 : !llvm.ptr -> i64
    %668 = arith.constant 2 : i32
    %670 = arith.extsi %668 : i32 to i64
    %669 = arith.divsi %667, %670 : i64
    %671 = arith.remsi %669, %426 : i64
    %672 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %673 = llvm.call @printf(%672, %671) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %674 = arith.constant 0 : i32
    func.return %674 : i32
  }
}