Problem 833

S(10^35) mod 136101521. Uses i128 for exact comparison (10^35 fits in i128) and modular arithmetic for the sum.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 833: Square Triangle Products
# S(10^35) mod 136101521.
# Uses i128 for exact comparison (10^35 fits in i128) and modular arithmetic for the sum.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>)
    function printf(fmt: ptr<i8>, ...) -> i32
    function log(x: f64) -> f64
    function exp(x: f64) -> f64
}

const MOD: i64 = 136101521
const LOG10_35: f64 = 35.0 * 2.302585092994046

function gcd_ll(a: i64, b: i64) -> i64 {
    let mut x: i64 = a
    if x < 0 { x = 0 - x }
    let mut y: i64 = b
    if y < 0 { y = 0 - y }
    while y != 0 {
        let t: i64 = x % y
        x = y
        y = t
    }
    return x
}

function mod_pow(a: i64, e: i64, m: i64) -> i64 {
    let mut r: i64 = 1 % m
    let mut x: i64 = a % m
    if x < 0 { x = x + m }
    let mut ee: i64 = e
    while ee > 0 {
        if (ee & 1) == 1 { r = r * x % m }
        x = x * x % m
        ee = ee >> 1
    }
    return r
}

function mod_inv(a: i64, m: i64) -> i64 {
    return mod_pow(a, m - 2, m)
}

# Compute U_k(P) mod MOD using recurrence U_0=0, U_1=1, U_k = P*U_{k-1} - U_{k-2}
function lucas_U_mod(P: i64, k: i32) -> i64 {
    if k == 0 { return 0 }
    if k == 1 { return 1 % MOD }
    let Pm: i64 = P % MOD
    if Pm < 0 { Pm = Pm + MOD }
    let mut u0: i64 = 0
    let mut u1: i64 = 1 % MOD
    let mut kk: i32 = 2
    while kk <= k {
        let tmp: i64 = (Pm * u1 % MOD - u0 % MOD + MOD) % MOD
        u0 = u1
        u1 = tmp
        kk = kk + 1
    }
    return u1
}

# Compute log(c_value(n, i, j)) approximately using f64
# c_value = T(n) * U_i(4n+2) * U_j(4n+2)
# log(c_value) = log(T(n)) + log(U_i) + log(U_j)
function log_lucas_U(P: f64, k: i32) -> f64 {
    if k == 0 { return -1e300 }
    if k == 1 { return 0.0 }
    let mut u0: f64 = 0.0
    let mut u1: f64 = 1.0
    let mut l0: f64 = -1e300
    let mut l1: f64 = 0.0
    let mut kk: i32 = 2
    while kk <= k {
        let tmp: f64 = P * u1 - u0
        l0 = l1
        if tmp > 0.0 {
            l1 = log(P) + l1
            if l0 > -1e200 {
                let correction: f64 = 1.0 - exp(l0 - l1)
                if correction > 1e-15 { l1 = l1 + log(correction) }
            }
        } else {
            l1 = -1e300
        }
        u0 = u1
        u1 = tmp
        kk = kk + 1
    }
    return l1
}

function log_c_value(n: i64, i: i32, j: i32) -> f64 {
    if n <= 0 { return -1e300 }
    let tn: f64 = (n as f64) * ((n + 1) as f64) / 2.0
    let P: f64 = (4 * n + 2) as f64
    let li: f64 = log_lucas_U(P, i)
    let lj: f64 = log_lucas_U(P, j)
    return log(tn) + li + lj
}

# Compute c_value(n, i, j) using i128 with overflow detection
# Returns a value > N if overflow would occur or value exceeds CAP
const I128_CAP: i128 = 10000000000000000000000000000000000000

function abs_i128(x: i128) -> i128 {
    if x < 0 { return 0 - x }
    return x
}

function mul_overflow(a: i128, b: i128) -> i128 {
    # Returns a*b if |a*b| < I128_CAP, else I128_CAP
    if a == 0 { return 0 }
    if b == 0 { return 0 }
    let aa: i128 = abs_i128(a)
    let bb: i128 = abs_i128(b)
    if aa > (I128_CAP / bb) { return I128_CAP }
    return a * b
}

function c_value_i128(n: i64, i: i32, j: i32, ui: ptr<i128>, uj: ptr<i128>) -> i128 {
    if n <= 0 {
        ui[0] = 0
        uj[0] = 0
        return 0
    }
    let P: i128 = (4 * n + 2) as i128
    let mut u0: i128 = 0
    let mut u1: i128 = 1
    let mut ri: i128 = 0
    let mut rj: i128 = 0
    if i == 0 { ri = 0 } else { if i == 1 { ri = 1 } else { ri = 0 } }
    if j == 0 { rj = 0 } else { if j == 1 { rj = 1 } else { rj = 0 } }
    let mut k: i32 = 2
    while k <= i || k <= j {
        let tmp: i128 = mul_overflow(P, u1)
        if tmp == I128_CAP {
            ui[0] = I128_CAP
            uj[0] = I128_CAP
            return I128_CAP
        }
        let new_u1: i128 = tmp - u0
        if abs_i128(new_u1) > I128_CAP {
            ui[0] = I128_CAP
            uj[0] = I128_CAP
            return I128_CAP
        }
        u0 = u1
        u1 = new_u1
        if k == i { ri = u1 }
        if k == j { rj = u1 }
        k = k + 1
    }
    ui[0] = ri
    uj[0] = rj
    let tn: i128 = (n as i128) * ((n + 1) as i128) / 2
    let prod: i128 = mul_overflow(tn, ri)
    if prod == I128_CAP { return I128_CAP }
    let prod2: i128 = mul_overflow(prod, rj)
    if prod2 == I128_CAP { return I128_CAP }
    return prod2
}

# N = 10^35 as i128
function get_N_i128() -> i128 {
    # 10^35 = 100000000000000000000000000000000000
    # Split: 10^35 = 10^17 * 10^18
    # 10^17 = 100000000000000000
    # 10^18 = 1000000000000000000
    # But 10^17 * 10^18 = 10^35 which fits in i128
    let a: i128 = 100000000000000000
    let b: i128 = 1000000000000000000
    return a * b
}

# Find M = max n such that c_value(n, i, j) <= 10^35
# Use i128 binary search directly with overflow detection
function max_n_for_pair(i: i32, j: i32) -> i64 {
    let N: i128 = get_N_i128()

    let ui: ptr<i128> = calloc(2, 16)
    let uj: ptr<i128> = calloc(2, 16)

    # Check n=1
    let cv1: i128 = c_value_i128(1, i, j, ui, uj)
    if cv1 > N {
        free(ui as ptr<void>)
        free(uj as ptr<void>)
        return 0
    }

    # Exponential search for upper bound using f64 log
    let mut hi: i64 = 2
    while log_c_value(hi, i, j) < LOG10_35 {
        hi = hi * 2
        if hi > 10000000000000 { hi = 10000000000000; break }
    }

    # Binary search using i128 exact comparison
    let mut lo: i64 = 1
    while lo + 1 < hi {
        let mid: i64 = (lo + hi) / 2
        let cv: i128 = c_value_i128(mid, i, j, ui, uj)
        if cv <= N {
            lo = mid
        } else {
            hi = mid
        }
    }

    # Verify lo with i128
    let cv_lo: i128 = c_value_i128(lo, i, j, ui, uj)
    let M: i64 = if cv_lo <= N { lo } else { lo - 1 }

    free(ui as ptr<void>)
    free(uj as ptr<void>)
    return M
}

# Compute C(n, k) mod MOD
function binom_mod(n: i64, k: i32) -> i64 {
    if k < 0 { return 0 }
    if k == 0 { return 1 % MOD }
    let nn: i64 = n % MOD
    if nn < 0 { nn = nn + MOD }
    let mut result: i64 = 1
    let mut t: i32 = 0
    while t < k {
        let nt: i64 = (nn - (t as i64)) % MOD
        if nt < 0 { nt = nt + MOD }
        result = result * nt % MOD
        t = t + 1
    }
    # Divide by k! mod MOD
    let mut kf: i64 = 1
    let mut t2: i32 = 1
    while t2 <= k {
        kf = kf * (t2 as i64) % MOD
        t2 = t2 + 1
    }
    return result * mod_inv(kf, MOD) % MOD
}

# Compute sum_{n=0..M} f(n) mod MOD using Newton forward differences
# f(n) = c_value(n, i, j) mod MOD
function sum_for_pair(i: i32, j: i32, M: i64) -> i64 {
    let deg: i32 = i + j

    # Compute f(n) mod MOD for n = 0..deg
    let fvals: ptr<i64> = calloc((deg + 1) as i64, 8)
    let mut n: i64 = 0
    while n <= (deg as i64) {
        let P: i64 = (4 * n + 2) % MOD
        if P < 0 { P = P + MOD }
        let mut u0: i64 = 0
        let mut u1: i64 = 1 % MOD
        let mut ri: i64 = 0
        let mut rj: i64 = 0
        if i == 0 { ri = 0 } else { if i == 1 { ri = 1 % MOD } else { ri = 0 } }
        if j == 0 { rj = 0 } else { if j == 1 { rj = 1 % MOD } else { rj = 0 } }
        let mut k: i32 = 2
        while k <= i || k <= j {
            let tmp: i64 = (P * u1 % MOD - u0 % MOD + MOD) % MOD
            u0 = u1
            u1 = tmp
            if k == i { ri = u1 }
            if k == j { rj = u1 }
            k = k + 1
        }
        let tn: i64 = (n % MOD) * ((n + 1) % MOD) % MOD * mod_inv(2, MOD) % MOD
        fvals[n] = tn * ri % MOD * rj % MOD
        n = n + 1
    }

    # Forward differences
    let a: ptr<i64> = calloc((deg + 1) as i64, 8)
    let cur: ptr<i64> = calloc((deg + 1) as i64, 8)
    let mut x: i64 = 0
    while x <= (deg as i64) { cur[x] = fvals[x]; x = x + 1 }
    let mut nn: i32 = deg + 1
    let mut ci: i32 = 0
    while nn > 0 {
        a[ci] = cur[0]
        ci = ci + 1
        let mut k: i32 = 0
        while k < nn - 1 {
            cur[k] = (cur[k + 1] - cur[k] % MOD + MOD) % MOD
            k = k + 1
        }
        nn = nn - 1
    }

    # Sum = sum_{m=0..deg} a[m] * C(M+1, m+1) mod MOD
    let mut result: i64 = 0
    let Mp1: i64 = M + 1
    let mut m: i32 = 0
    while m <= deg {
        let binom: i64 = binom_mod(Mp1, m + 1)
        let term: i64 = a[m] % MOD * binom % MOD
        result = (result + term) % MOD
        m = m + 1
    }

    free(fvals as ptr<void>)
    free(a as ptr<void>)
    free(cur as ptr<void>)
    return result
}

# Find max j such that U_j(6) <= 10^35
function maxJ_for_N() -> i32 {
    let N: i128 = get_N_i128()
    let P: i128 = 6
    let mut u0: i128 = 0
    let mut u1: i128 = 1
    let mut maxj: i32 = 1
    let mut k: i32 = 2
    while k < 400 {
        let tmp: i128 = P * u1 - u0
        u0 = u1
        u1 = tmp
        if u1 > N { break }
        maxj = k
        k = k + 1
    }
    return maxj
}

function main() -> i32 {
    let maxj: i32 = maxJ_for_N()
    let mut total: i64 = 0

    let mut i: i32 = 1
    while i < maxj {
        let mut j: i32 = i + 1
        while j <= maxj {
            if gcd_ll(i as i64, j as i64) == 1 {
                let M: i64 = max_n_for_pair(i, j)
                if M > 0 {
                    let s: i64 = sum_for_pair(i, j, M)
                    total = (total + s) % MOD
                }
            }
            j = j + 1
        }
        i = i + 1
    }

    printf("%lld\n", total)
    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_ll_i64_i64(int64_t a, int64_t b);
int64_t mod_pow_i64_i64_i64(int64_t a, int64_t e, int64_t m);
int64_t mod_inv_i64_i64(int64_t a, int64_t m);
int64_t lucas_U_mod_i64_i32(int64_t P, int32_t k);
double log_lucas_U_f64_i32(double P, int32_t k);
double log_c_value_i64_i32_i32(int64_t n, int32_t i, int32_t j);
__int128 abs_i128_i128(__int128 x);
__int128 mul_overflow_i128_i128(__int128 a, __int128 b);
__int128 c_value_i128_i64_i32_i32_ptr_i128_ptr_i128(int64_t n, int32_t i, int32_t j, __int128* ui, __int128* uj);
__int128 get_N_i128(void);
int64_t max_n_for_pair_i32_i32(int32_t i, int32_t j);
int64_t binom_mod_i64_i32(int64_t n, int32_t k);
int64_t sum_for_pair_i32_i32_i64(int32_t i, int32_t j, int64_t M);
int32_t maxJ_for_N(void);
int32_t main(void);

static const int64_t MOD = 136101521;
static const double LOG10_35 = (35.0 * 2.302585092994046);
static const __int128 I128_CAP = ((__int128)0x785EE10D5DA46D9ULL << 64 | (__int128)0xF436A000000000ULL);






int64_t gcd_ll_i64_i64(int64_t a, int64_t b) {
    int64_t x = a;
    if (x < 0) {
        x = (0 - x);
    }
    int64_t y = b;
    if (y < 0) {
        y = (0 - y);
    }
    while (y != 0) {
        int64_t t = FLOW_CHECKED_MOD((x), (y));
        x = y;
        y = t;
    }
    return x;
}

int64_t mod_pow_i64_i64_i64(int64_t a, int64_t e, int64_t m) {
    int64_t r = FLOW_CHECKED_MOD((1), (m));
    int64_t x = FLOW_CHECKED_MOD((a), (m));
    if (x < 0) {
        x = (x + m);
    }
    int64_t ee = e;
    while (ee > 0) {
        if ((ee & 1) == 1) {
            r = FLOW_CHECKED_MOD(((r * x)), (m));
        }
        x = FLOW_CHECKED_MOD(((x * x)), (m));
        ee = FLOW_CHECKED_SHR((ee), (1));
    }
    return r;
}

int64_t mod_inv_i64_i64(int64_t a, int64_t m) {
    return mod_pow_i64_i64_i64(a, (m - 2), m);
}

int64_t lucas_U_mod_i64_i32(int64_t P, int32_t k) {
    if (k == 0) {
        return 0;
    }
    if (k == 1) {
        return FLOW_CHECKED_MOD((1), (MOD));
    }
    int64_t Pm = FLOW_CHECKED_MOD((P), (MOD));
    if (Pm < 0) {
        Pm = (Pm + MOD);
    }
    int64_t u0 = 0;
    int64_t u1 = FLOW_CHECKED_MOD((1), (MOD));
    int32_t kk = 2;
    while (kk <= k) {
        int64_t tmp = FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((Pm * u1)), (MOD)) - FLOW_CHECKED_MOD((u0), (MOD))) + MOD)), (MOD));
        u0 = u1;
        u1 = tmp;
        kk = (kk + 1);
    }
    return u1;
}

double log_lucas_U_f64_i32(double P, int32_t k) {
    if (k == 0) {
        return (-1e300);
    }
    if (k == 1) {
        return 0.0;
    }
    double u0 = 0.0;
    double u1 = 1.0;
    double l0 = (-1e300);
    double l1 = 0.0;
    int32_t kk = 2;
    while (kk <= k) {
        double tmp = ((P * u1) - u0);
        l0 = l1;
        if (tmp > 0.0) {
            l1 = (log(P) + l1);
            if (l0 > (-1e200)) {
                double correction = (1.0 - exp((l0 - l1)));
                if (correction > 1e-15) {
                    l1 = (l1 + log(correction));
                }
            }
        } else {
            l1 = (-1e300);
        }
        u0 = u1;
        u1 = tmp;
        kk = (kk + 1);
    }
    return l1;
}

double log_c_value_i64_i32_i32(int64_t n, int32_t i, int32_t j) {
    if (n <= 0) {
        return (-1e300);
    }
    double tn = ((((double)(n)) * ((double)((n + 1)))) / 2.0);
    double P = ((double)(((4 * n) + 2)));
    double li = log_lucas_U_f64_i32(P, i);
    double lj = log_lucas_U_f64_i32(P, j);
    return ((log(tn) + li) + lj);
}

__int128 abs_i128_i128(__int128 x) {
    if (x < 0) {
        return (0 - x);
    }
    return x;
}

__int128 mul_overflow_i128_i128(__int128 a, __int128 b) {
    if (a == 0) {
        return 0;
    }
    if (b == 0) {
        return 0;
    }
    __int128 aa = abs_i128_i128(a);
    __int128 bb = abs_i128_i128(b);
    if (aa > FLOW_CHECKED_DIV((I128_CAP), (bb))) {
        return I128_CAP;
    }
    return (a * b);
}

__int128 c_value_i128_i64_i32_i32_ptr_i128_ptr_i128(int64_t n, int32_t i, int32_t j, __int128* ui, __int128* uj) {
    if (n <= 0) {
        ui[0] = 0;
        uj[0] = 0;
        return 0;
    }
    __int128 P = ((__int128)(((4 * n) + 2)));
    __int128 u0 = 0;
    __int128 u1 = 1;
    __int128 ri = 0;
    __int128 rj = 0;
    if (i == 0) {
        ri = 0;
    } else {
        if (i == 1) {
            ri = 1;
        } else {
            ri = 0;
        }
    }
    if (j == 0) {
        rj = 0;
    } else {
        if (j == 1) {
            rj = 1;
        } else {
            rj = 0;
        }
    }
    int32_t k = 2;
    while ((k <= i || k <= j)) {
        __int128 tmp = mul_overflow_i128_i128(P, u1);
        if (tmp == I128_CAP) {
            ui[0] = I128_CAP;
            uj[0] = I128_CAP;
            return I128_CAP;
        }
        __int128 new_u1 = (tmp - u0);
        if (abs_i128_i128(new_u1) > I128_CAP) {
            ui[0] = I128_CAP;
            uj[0] = I128_CAP;
            return I128_CAP;
        }
        u0 = u1;
        u1 = new_u1;
        if (k == i) {
            ri = u1;
        }
        if (k == j) {
            rj = u1;
        }
        k = (k + 1);
    }
    ui[0] = ri;
    uj[0] = rj;
    __int128 tn = FLOW_CHECKED_DIV(((((__int128)(n)) * ((__int128)((n + 1))))), (2));
    __int128 prod = mul_overflow_i128_i128(tn, ri);
    if (prod == I128_CAP) {
        return I128_CAP;
    }
    __int128 prod2 = mul_overflow_i128_i128(prod, rj);
    if (prod2 == I128_CAP) {
        return I128_CAP;
    }
    return prod2;
}

__int128 get_N_i128(void) {
    __int128 a = 100000000000000000;
    __int128 b = 1000000000000000000;
    return (a * b);
}

int64_t max_n_for_pair_i32_i32(int32_t i, int32_t j) {
    __int128 N = get_N_i128();
    __int128* ui = (__int128*)(calloc(2, 16));
    __int128* uj = (__int128*)(calloc(2, 16));
    __int128 cv1 = c_value_i128_i64_i32_i32_ptr_i128_ptr_i128(1, i, j, ui, uj);
    if (cv1 > N) {
        free(((void*)(ui)));
        free(((void*)(uj)));
        return 0;
    }
    int64_t hi = 2;
    while (log_c_value_i64_i32_i32(hi, i, j) < LOG10_35) {
        hi = (hi * 2);
        if (hi > 10000000000000) {
            hi = 10000000000000;
            break;
        }
    }
    int64_t lo = 1;
    while ((lo + 1) < hi) {
        int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
        __int128 cv = c_value_i128_i64_i32_i32_ptr_i128_ptr_i128(mid, i, j, ui, uj);
        if (cv <= N) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    __int128 cv_lo = c_value_i128_i64_i32_i32_ptr_i128_ptr_i128(lo, i, j, ui, uj);
    int64_t M = ((cv_lo <= N) ? (lo) : ((lo - 1)));
    free(((void*)(ui)));
    free(((void*)(uj)));
    return M;
}

int64_t binom_mod_i64_i32(int64_t n, int32_t k) {
    if (k < 0) {
        return 0;
    }
    if (k == 0) {
        return FLOW_CHECKED_MOD((1), (MOD));
    }
    int64_t nn = FLOW_CHECKED_MOD((n), (MOD));
    if (nn < 0) {
        nn = (nn + MOD);
    }
    int64_t result = 1;
    int32_t t = 0;
    while (t < k) {
        int64_t nt = FLOW_CHECKED_MOD(((nn - ((int64_t)(t)))), (MOD));
        if (nt < 0) {
            nt = (nt + MOD);
        }
        result = FLOW_CHECKED_MOD(((result * nt)), (MOD));
        t = (t + 1);
    }
    int64_t kf = 1;
    int32_t t2 = 1;
    while (t2 <= k) {
        kf = FLOW_CHECKED_MOD(((kf * ((int64_t)(t2)))), (MOD));
        t2 = (t2 + 1);
    }
    return FLOW_CHECKED_MOD(((result * mod_inv_i64_i64(kf, MOD))), (MOD));
}

int64_t sum_for_pair_i32_i32_i64(int32_t i, int32_t j, int64_t M) {
    int32_t deg = (i + j);
    int64_t* fvals = (int64_t*)(calloc(((int64_t)((deg + 1))), 8));
    int64_t n = 0;
    while (n <= ((int64_t)(deg))) {
        int64_t P = FLOW_CHECKED_MOD((((4 * n) + 2)), (MOD));
        if (P < 0) {
            P = (P + MOD);
        }
        int64_t u0 = 0;
        int64_t u1 = FLOW_CHECKED_MOD((1), (MOD));
        int64_t ri = 0;
        int64_t rj = 0;
        if (i == 0) {
            ri = 0;
        } else {
            if (i == 1) {
                ri = FLOW_CHECKED_MOD((1), (MOD));
            } else {
                ri = 0;
            }
        }
        if (j == 0) {
            rj = 0;
        } else {
            if (j == 1) {
                rj = FLOW_CHECKED_MOD((1), (MOD));
            } else {
                rj = 0;
            }
        }
        int32_t k = 2;
        while ((k <= i || k <= j)) {
            int64_t tmp = FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((P * u1)), (MOD)) - FLOW_CHECKED_MOD((u0), (MOD))) + MOD)), (MOD));
            u0 = u1;
            u1 = tmp;
            if (k == i) {
                ri = u1;
            }
            if (k == j) {
                rj = u1;
            }
            k = (k + 1);
        }
        int64_t tn = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((n), (MOD)) * FLOW_CHECKED_MOD(((n + 1)), (MOD)))), (MOD)) * mod_inv_i64_i64(2, MOD))), (MOD));
        fvals[n] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((tn * ri)), (MOD)) * rj)), (MOD));
        n = (n + 1);
    }
    int64_t* a = (int64_t*)(calloc(((int64_t)((deg + 1))), 8));
    int64_t* cur = (int64_t*)(calloc(((int64_t)((deg + 1))), 8));
    int64_t x = 0;
    while (x <= ((int64_t)(deg))) {
        cur[x] = fvals[x];
        x = (x + 1);
    }
    int32_t nn = (deg + 1);
    int32_t ci = 0;
    while (nn > 0) {
        a[ci] = cur[0];
        ci = (ci + 1);
        int32_t k = 0;
        while (k < (nn - 1)) {
            cur[k] = FLOW_CHECKED_MOD((((cur[(k + 1)] - FLOW_CHECKED_MOD((cur[k]), (MOD))) + MOD)), (MOD));
            k = (k + 1);
        }
        nn = (nn - 1);
    }
    int64_t result = 0;
    int64_t Mp1 = (M + 1);
    int32_t m = 0;
    while (m <= deg) {
        int64_t binom = binom_mod_i64_i32(Mp1, (m + 1));
        int64_t term = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a[m]), (MOD)) * binom)), (MOD));
        result = FLOW_CHECKED_MOD(((result + term)), (MOD));
        m = (m + 1);
    }
    free(((void*)(fvals)));
    free(((void*)(a)));
    free(((void*)(cur)));
    return result;
}

int32_t maxJ_for_N(void) {
    __int128 N = get_N_i128();
    __int128 P = 6;
    __int128 u0 = 0;
    __int128 u1 = 1;
    int32_t maxj = 1;
    int32_t k = 2;
    while (k < 400) {
        __int128 tmp = ((P * u1) - u0);
        u0 = u1;
        u1 = tmp;
        if (u1 > N) {
            break;
        }
        maxj = k;
        k = (k + 1);
    }
    return maxj;
}

int32_t main(void) {
    int32_t maxj = maxJ_for_N();
    int64_t total = 0;
    int32_t i = 1;
    while (i < maxj) {
        int32_t j = (i + 1);
        while (j <= maxj) {
            if (gcd_ll_i64_i64(((int64_t)(i)), ((int64_t)(j))) == 1) {
                int64_t M = max_n_for_pair_i32_i32(i, j);
                if (M > 0) {
                    int64_t s = sum_for_pair_i32_i32_i64(i, j, M);
                    total = FLOW_CHECKED_MOD(((total + s)), (MOD));
                }
            }
            j = (j + 1);
        }
        i = (i + 1);
    }
    printf("%lld\n", total);
    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 private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()

  func.func private @log(f64) -> f64
  func.func private @exp(f64) -> f64
  // Constant: MOD
  llvm.mlir.global internal constant @MOD(136101521 : i64) : i64
  // Constant: LOG10_35
  llvm.mlir.global internal constant @LOG10_35(0.0 : f64) : f64
  func.func @gcd_ll(%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.load %1 : !llvm.ptr -> i64
    %3 = arith.constant 0 : i32
    %5 = arith.extsi %3 : i32 to i64
    %4 = arith.cmpi slt, %2, %5 : i64
    cf.cond_br %4, ^bb0, ^bb1
    ^bb0:
      %6 = arith.constant 0 : i32
      %7 = llvm.load %1 : !llvm.ptr -> i64
      %9 = arith.extsi %6 : i32 to i64
      %8 = arith.subi %9, %7 : i64
      llvm.store %8, %1 : i64, !llvm.ptr
      cf.br ^bb2
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %10 = llvm.mlir.constant(1 : i64) : i64
    %11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %11 : i64, !llvm.ptr
    %12 = llvm.load %11 : !llvm.ptr -> i64
    %13 = arith.constant 0 : i32
    %15 = arith.extsi %13 : i32 to i64
    %14 = arith.cmpi slt, %12, %15 : i64
    cf.cond_br %14, ^bb3, ^bb4
    ^bb3:
      %16 = arith.constant 0 : i32
      %17 = llvm.load %11 : !llvm.ptr -> i64
      %19 = arith.extsi %16 : i32 to i64
      %18 = arith.subi %19, %17 : i64
      llvm.store %18, %11 : i64, !llvm.ptr
      cf.br ^bb5
    ^bb4:
      cf.br ^bb5
    ^bb5:
    cf.br ^bb6
    ^bb6:
    %20 = llvm.load %11 : !llvm.ptr -> i64
    %21 = arith.constant 0 : i32
    %23 = arith.extsi %21 : i32 to i64
    %22 = arith.cmpi ne, %20, %23 : i64
    cf.cond_br %22, ^bb7, ^bb8
    ^bb7:
      %24 = llvm.load %1 : !llvm.ptr -> i64
      %25 = llvm.load %11 : !llvm.ptr -> i64
      %26 = arith.remsi %24, %25 : i64
      %27 = llvm.load %11 : !llvm.ptr -> i64
      llvm.store %27, %1 : i64, !llvm.ptr
      llvm.store %26, %11 : i64, !llvm.ptr
      cf.br ^bb6
    ^bb8:
    %28 = llvm.load %1 : !llvm.ptr -> i64
    func.return %28 : i64
  }
  func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %29 = arith.constant 1 : i32
    %31 = arith.extsi %29 : i32 to i64
    %30 = arith.remsi %31, %arg2 : i64
    %32 = llvm.mlir.constant(1 : i64) : i64
    %33 = llvm.alloca %32 x i64 : (i64) -> !llvm.ptr
    llvm.store %30, %33 : i64, !llvm.ptr
    %34 = arith.remsi %arg0, %arg2 : i64
    %35 = llvm.mlir.constant(1 : i64) : i64
    %36 = llvm.alloca %35 x i64 : (i64) -> !llvm.ptr
    llvm.store %34, %36 : i64, !llvm.ptr
    %37 = llvm.load %36 : !llvm.ptr -> i64
    %38 = arith.constant 0 : i32
    %40 = arith.extsi %38 : i32 to i64
    %39 = arith.cmpi slt, %37, %40 : i64
    cf.cond_br %39, ^bb9, ^bb10
    ^bb9:
      %41 = llvm.load %36 : !llvm.ptr -> i64
      %42 = arith.addi %41, %arg2 : i64
      llvm.store %42, %36 : i64, !llvm.ptr
      cf.br ^bb11
    ^bb10:
      cf.br ^bb11
    ^bb11:
    %43 = llvm.mlir.constant(1 : i64) : i64
    %44 = llvm.alloca %43 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %44 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %45 = llvm.load %44 : !llvm.ptr -> i64
    %46 = arith.constant 0 : i32
    %48 = arith.extsi %46 : i32 to i64
    %47 = arith.cmpi sgt, %45, %48 : i64
    cf.cond_br %47, ^bb13, ^bb14
    ^bb13:
      %49 = llvm.load %44 : !llvm.ptr -> i64
      %50 = arith.constant 1 : i32
      %52 = arith.extsi %50 : i32 to i64
      %51 = arith.andi %49, %52 : i64
      %53 = arith.constant 1 : i32
      %55 = arith.extsi %53 : i32 to i64
      %54 = arith.cmpi eq, %51, %55 : i64
      cf.cond_br %54, ^bb15, ^bb16
      ^bb15:
        %56 = llvm.load %33 : !llvm.ptr -> i64
        %57 = llvm.load %36 : !llvm.ptr -> i64
        %58 = arith.muli %56, %57 : i64
        %59 = arith.remsi %58, %arg2 : i64
        llvm.store %59, %33 : i64, !llvm.ptr
        cf.br ^bb17
      ^bb16:
        cf.br ^bb17
      ^bb17:
      %60 = llvm.load %36 : !llvm.ptr -> i64
      %61 = llvm.load %36 : !llvm.ptr -> i64
      %62 = arith.muli %60, %61 : i64
      %63 = arith.remsi %62, %arg2 : i64
      llvm.store %63, %36 : i64, !llvm.ptr
      %64 = llvm.load %44 : !llvm.ptr -> i64
      %65 = arith.constant 1 : i32
      %67 = arith.extsi %65 : i32 to i64
      %66 = arith.shrsi %64, %67 : i64
      llvm.store %66, %44 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %68 = llvm.load %33 : !llvm.ptr -> i64
    func.return %68 : i64
  }
  func.func @mod_inv(%arg0: i64, %arg1: i64) -> i64 {
    %70 = arith.constant 2 : i32
    %72 = arith.extsi %70 : i32 to i64
    %71 = arith.subi %arg1, %72 : i64
    %69 = func.call @mod_pow(%arg0, %71, %arg1) : (i64, i64, i64) -> i64
    func.return %69 : i64
  }
  func.func @lucas_U_mod(%arg0: i64, %arg1: i32) -> i64 {
    %73 = arith.constant 0 : i32
    %74 = arith.cmpi eq, %arg1, %73 : i32
    cf.cond_br %74, ^bb18, ^bb19
    ^bb18:
      %75 = arith.constant 0 : i32
      %76 = arith.extsi %75 : i32 to i64
      func.return %76 : i64
    ^bb19:
      cf.br ^bb20
    ^bb20:
    %77 = arith.constant 1 : i32
    %78 = arith.cmpi eq, %arg1, %77 : i32
    cf.cond_br %78, ^bb21, ^bb22
    ^bb21:
      %79 = arith.constant 1 : i32
      %80 = llvm.mlir.addressof @MOD : !llvm.ptr
      %81 = llvm.load %80 : !llvm.ptr -> i64
      %83 = arith.extsi %79 : i32 to i64
      %82 = arith.remsi %83, %81 : i64
      func.return %82 : i64
    ^bb22:
      cf.br ^bb23
    ^bb23:
    %84 = llvm.mlir.addressof @MOD : !llvm.ptr
    %85 = llvm.load %84 : !llvm.ptr -> i64
    %86 = arith.remsi %arg0, %85 : i64
    %87 = arith.constant 0 : i32
    %89 = arith.extsi %87 : i32 to i64
    %88 = arith.cmpi slt, %86, %89 : i64
    %90 = scf.if %88 -> (i64) {
      %91 = llvm.mlir.addressof @MOD : !llvm.ptr
      %92 = llvm.load %91 : !llvm.ptr -> i64
      %93 = arith.addi %86, %92 : i64
      scf.yield %93 : i64
    } else {
      scf.yield %86 : i64
    }
    %94 = arith.constant 0 : i32
    %95 = arith.extsi %94 : i32 to i64
    %96 = llvm.mlir.constant(1 : i64) : i64
    %97 = llvm.alloca %96 x i64 : (i64) -> !llvm.ptr
    llvm.store %95, %97 : i64, !llvm.ptr
    %98 = arith.constant 1 : i32
    %99 = llvm.mlir.addressof @MOD : !llvm.ptr
    %100 = llvm.load %99 : !llvm.ptr -> i64
    %102 = arith.extsi %98 : i32 to i64
    %101 = arith.remsi %102, %100 : i64
    %103 = llvm.mlir.constant(1 : i64) : i64
    %104 = llvm.alloca %103 x i64 : (i64) -> !llvm.ptr
    llvm.store %101, %104 : i64, !llvm.ptr
    %105 = arith.constant 2 : i32
    %106 = llvm.mlir.constant(1 : i64) : i64
    %107 = llvm.alloca %106 x i32 : (i64) -> !llvm.ptr
    llvm.store %105, %107 : i32, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %108 = llvm.load %107 : !llvm.ptr -> i32
    %109 = arith.cmpi sle, %108, %arg1 : i32
    cf.cond_br %109, ^bb25, ^bb26
    ^bb25:
      %110 = llvm.load %104 : !llvm.ptr -> i64
      %111 = arith.muli %90, %110 : i64
      %112 = llvm.mlir.addressof @MOD : !llvm.ptr
      %113 = llvm.load %112 : !llvm.ptr -> i64
      %114 = arith.remsi %111, %113 : i64
      %115 = llvm.load %97 : !llvm.ptr -> i64
      %116 = llvm.mlir.addressof @MOD : !llvm.ptr
      %117 = llvm.load %116 : !llvm.ptr -> i64
      %118 = arith.remsi %115, %117 : i64
      %119 = arith.subi %114, %118 : i64
      %120 = llvm.mlir.addressof @MOD : !llvm.ptr
      %121 = llvm.load %120 : !llvm.ptr -> i64
      %122 = arith.addi %119, %121 : i64
      %123 = llvm.mlir.addressof @MOD : !llvm.ptr
      %124 = llvm.load %123 : !llvm.ptr -> i64
      %125 = arith.remsi %122, %124 : i64
      %126 = llvm.load %104 : !llvm.ptr -> i64
      llvm.store %126, %97 : i64, !llvm.ptr
      llvm.store %125, %104 : i64, !llvm.ptr
      %127 = llvm.load %107 : !llvm.ptr -> i32
      %128 = arith.constant 1 : i32
      %129 = arith.addi %127, %128 : i32
      llvm.store %129, %107 : i32, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    %130 = llvm.load %104 : !llvm.ptr -> i64
    func.return %130 : i64
  }
  func.func @log_lucas_U(%arg0: f64, %arg1: i32) -> f64 {
    %131 = arith.constant 0 : i32
    %132 = arith.cmpi eq, %arg1, %131 : i32
    cf.cond_br %132, ^bb27, ^bb28
    ^bb27:
      %133 = arith.constant 1000000000000000052504760255204420248704468581108159154915854115511802457988908195786371375080447864043704443832883878176942523235360430575644792184786706982848387200926575803737830233794788090059368953234970799945081119038967640880074652742780142494579258788820056842838115669472196386865459400540160 : f32
      %134 = arith.negf %133 : f32
      %135 = arith.extf %134 : f32 to f64
      func.return %135 : f64
    ^bb28:
      cf.br ^bb29
    ^bb29:
    %136 = arith.constant 1 : i32
    %137 = arith.cmpi eq, %arg1, %136 : i32
    cf.cond_br %137, ^bb30, ^bb31
    ^bb30:
      %138 = arith.constant 0.0 : f32
      %139 = arith.extf %138 : f32 to f64
      func.return %139 : f64
    ^bb31:
      cf.br ^bb32
    ^bb32:
    %140 = arith.constant 0.0 : f32
    %141 = arith.extf %140 : f32 to f64
    %142 = llvm.mlir.constant(1 : i64) : i64
    %143 = llvm.alloca %142 x f64 : (i64) -> !llvm.ptr
    llvm.store %141, %143 : f64, !llvm.ptr
    %144 = arith.constant 1.0 : f32
    %145 = arith.extf %144 : f32 to f64
    %146 = llvm.mlir.constant(1 : i64) : i64
    %147 = llvm.alloca %146 x f64 : (i64) -> !llvm.ptr
    llvm.store %145, %147 : f64, !llvm.ptr
    %148 = arith.constant 1000000000000000052504760255204420248704468581108159154915854115511802457988908195786371375080447864043704443832883878176942523235360430575644792184786706982848387200926575803737830233794788090059368953234970799945081119038967640880074652742780142494579258788820056842838115669472196386865459400540160 : f32
    %149 = arith.negf %148 : f32
    %150 = arith.extf %149 : f32 to f64
    %151 = llvm.mlir.constant(1 : i64) : i64
    %152 = llvm.alloca %151 x f64 : (i64) -> !llvm.ptr
    llvm.store %150, %152 : f64, !llvm.ptr
    %153 = arith.constant 0.0 : f32
    %154 = arith.extf %153 : f32 to f64
    %155 = llvm.mlir.constant(1 : i64) : i64
    %156 = llvm.alloca %155 x f64 : (i64) -> !llvm.ptr
    llvm.store %154, %156 : f64, !llvm.ptr
    %157 = arith.constant 2 : i32
    %158 = llvm.mlir.constant(1 : i64) : i64
    %159 = llvm.alloca %158 x i32 : (i64) -> !llvm.ptr
    llvm.store %157, %159 : i32, !llvm.ptr
    cf.br ^bb33
    ^bb33:
    %160 = llvm.load %159 : !llvm.ptr -> i32
    %161 = arith.cmpi sle, %160, %arg1 : i32
    cf.cond_br %161, ^bb34, ^bb35
    ^bb34:
      %162 = llvm.load %147 : !llvm.ptr -> f64
      %163 = arith.mulf %arg0, %162 : f64
      %164 = llvm.load %143 : !llvm.ptr -> f64
      %165 = arith.subf %163, %164 : f64
      %166 = llvm.load %156 : !llvm.ptr -> f64
      llvm.store %166, %152 : f64, !llvm.ptr
      %167 = arith.constant 0.0 : f32
      %169 = arith.extf %167 : f32 to f64
      %168 = arith.cmpf ogt, %165, %169 : f64
      cf.cond_br %168, ^bb36, ^bb37
      ^bb36:
        %170 = math.log %arg0 : f64
        %171 = llvm.load %156 : !llvm.ptr -> f64
        %172 = arith.addf %170, %171 : f64
        llvm.store %172, %156 : f64, !llvm.ptr
        %173 = llvm.load %152 : !llvm.ptr -> f64
        %174 = arith.constant 99999999999999996973312221251036165947450327545502362648241750950346848435554075534196338404706251868027512415973882408182135734368278484639385041047239877871023591066789981811181813306167128854888448 : f32
        %175 = arith.negf %174 : f32
        %177 = arith.extf %175 : f32 to f64
        %176 = arith.cmpf ogt, %173, %177 : f64
        cf.cond_br %176, ^bb39, ^bb40
        ^bb39:
          %178 = arith.constant 1.0 : f32
          %179 = llvm.load %152 : !llvm.ptr -> f64
          %180 = llvm.load %156 : !llvm.ptr -> f64
          %181 = arith.subf %179, %180 : f64
          %182 = math.exp %181 : f64
          %184 = arith.extf %178 : f32 to f64
          %183 = arith.subf %184, %182 : f64
          %185 = arith.constant 0 : f32
          %187 = arith.extf %185 : f32 to f64
          %186 = arith.cmpf ogt, %183, %187 : f64
          cf.cond_br %186, ^bb42, ^bb43
          ^bb42:
            %188 = llvm.load %156 : !llvm.ptr -> f64
            %189 = math.log %183 : f64
            %190 = arith.addf %188, %189 : f64
            llvm.store %190, %156 : f64, !llvm.ptr
            cf.br ^bb44
          ^bb43:
            cf.br ^bb44
          ^bb44:
          cf.br ^bb41
        ^bb40:
          cf.br ^bb41
        ^bb41:
        cf.br ^bb38
      ^bb37:
        %191 = arith.constant 1000000000000000052504760255204420248704468581108159154915854115511802457988908195786371375080447864043704443832883878176942523235360430575644792184786706982848387200926575803737830233794788090059368953234970799945081119038967640880074652742780142494579258788820056842838115669472196386865459400540160 : f32
        %192 = arith.negf %191 : f32
        %193 = arith.extf %192 : f32 to f64
        llvm.store %193, %156 : f64, !llvm.ptr
        cf.br ^bb38
      ^bb38:
      %194 = llvm.load %147 : !llvm.ptr -> f64
      llvm.store %194, %143 : f64, !llvm.ptr
      llvm.store %165, %147 : f64, !llvm.ptr
      %195 = llvm.load %159 : !llvm.ptr -> i32
      %196 = arith.constant 1 : i32
      %197 = arith.addi %195, %196 : i32
      llvm.store %197, %159 : i32, !llvm.ptr
      cf.br ^bb33
    ^bb35:
    %198 = llvm.load %156 : !llvm.ptr -> f64
    func.return %198 : f64
  }
  func.func @log_c_value(%arg0: i64, %arg1: i32, %arg2: i32) -> f64 {
    %199 = arith.constant 0 : i32
    %201 = arith.extsi %199 : i32 to i64
    %200 = arith.cmpi sle, %arg0, %201 : i64
    cf.cond_br %200, ^bb45, ^bb46
    ^bb45:
      %202 = arith.constant 1000000000000000052504760255204420248704468581108159154915854115511802457988908195786371375080447864043704443832883878176942523235360430575644792184786706982848387200926575803737830233794788090059368953234970799945081119038967640880074652742780142494579258788820056842838115669472196386865459400540160 : f32
      %203 = arith.negf %202 : f32
      %204 = arith.extf %203 : f32 to f64
      func.return %204 : f64
    ^bb46:
      cf.br ^bb47
    ^bb47:
    %205 = arith.sitofp %arg0 : i64 to f64
    %206 = arith.constant 1 : i32
    %208 = arith.extsi %206 : i32 to i64
    %207 = arith.addi %arg0, %208 : i64
    %209 = arith.sitofp %207 : i64 to f64
    %210 = arith.mulf %205, %209 : f64
    %211 = arith.constant 2.0 : f32
    %213 = arith.extf %211 : f32 to f64
    %212 = arith.divf %210, %213 : f64
    %214 = arith.constant 4 : i32
    %216 = arith.extsi %214 : i32 to i64
    %215 = arith.muli %216, %arg0 : i64
    %217 = arith.constant 2 : i32
    %219 = arith.extsi %217 : i32 to i64
    %218 = arith.addi %215, %219 : i64
    %220 = arith.sitofp %218 : i64 to f64
    %221 = func.call @log_lucas_U(%220, %arg1) : (f64, i32) -> f64
    %222 = func.call @log_lucas_U(%220, %arg2) : (f64, i32) -> f64
    %223 = math.log %212 : f64
    %224 = arith.addf %223, %221 : f64
    %225 = arith.addf %224, %222 : f64
    func.return %225 : f64
  }
  // Constant: I128_CAP
  llvm.mlir.global internal constant @I128_CAP(10000000000000000000000000000000000000 : i128) : i128
  func.func @abs_i128(%arg0: i128) -> i128 {
    %226 = arith.constant 0 : i32
    %228 = arith.trunci %arg0 : i128 to i64
    %229 = arith.extsi %226 : i32 to i64
    %227 = arith.cmpi slt, %228, %229 : i64
    cf.cond_br %227, ^bb48, ^bb49
    ^bb48:
      %230 = arith.constant 0 : i32
      %232 = arith.extsi %230 : i32 to i64
      %233 = arith.trunci %arg0 : i128 to i64
      %231 = arith.subi %232, %233 : i64
      %234 = arith.extsi %231 : i64 to i128
      func.return %234 : i128
    ^bb49:
      cf.br ^bb50
    ^bb50:
    func.return %arg0 : i128
  }
  func.func @mul_overflow(%arg0: i128, %arg1: i128) -> i128 {
    %235 = arith.constant 0 : i32
    %237 = arith.trunci %arg0 : i128 to i64
    %238 = arith.extsi %235 : i32 to i64
    %236 = arith.cmpi eq, %237, %238 : i64
    cf.cond_br %236, ^bb51, ^bb52
    ^bb51:
      %239 = arith.constant 0 : i32
      %240 = arith.extsi %239 : i32 to i128
      func.return %240 : i128
    ^bb52:
      cf.br ^bb53
    ^bb53:
    %241 = arith.constant 0 : i32
    %243 = arith.trunci %arg1 : i128 to i64
    %244 = arith.extsi %241 : i32 to i64
    %242 = arith.cmpi eq, %243, %244 : i64
    cf.cond_br %242, ^bb54, ^bb55
    ^bb54:
      %245 = arith.constant 0 : i32
      %246 = arith.extsi %245 : i32 to i128
      func.return %246 : i128
    ^bb55:
      cf.br ^bb56
    ^bb56:
    %247 = func.call @abs_i128(%arg0) : (i128) -> i128
    %248 = func.call @abs_i128(%arg1) : (i128) -> i128
    %249 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
    %250 = llvm.load %249 : !llvm.ptr -> i128
    %252 = arith.trunci %250 : i128 to i64
    %253 = arith.trunci %248 : i128 to i64
    %251 = arith.divsi %252, %253 : i64
    %255 = arith.trunci %247 : i128 to i64
    %254 = arith.cmpi sgt, %255, %251 : i64
    cf.cond_br %254, ^bb57, ^bb58
    ^bb57:
      %256 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
      %257 = llvm.load %256 : !llvm.ptr -> i128
      func.return %257 : i128
    ^bb58:
      cf.br ^bb59
    ^bb59:
    %259 = arith.trunci %arg0 : i128 to i64
    %260 = arith.trunci %arg1 : i128 to i64
    %258 = arith.muli %259, %260 : i64
    %261 = arith.extsi %258 : i64 to i128
    func.return %261 : i128
  }
  func.func @c_value_i128(%arg0: i64, %arg1: i32, %arg2: i32, %arg3: !llvm.ptr, %arg4: !llvm.ptr) -> i128 {
    %262 = arith.constant 0 : i32
    %264 = arith.extsi %262 : i32 to i64
    %263 = arith.cmpi sle, %arg0, %264 : i64
    cf.cond_br %263, ^bb60, ^bb61
    ^bb60:
      %265 = arith.constant 0 : i32
      %266 = arith.constant 0 : i32
      %267 = arith.extsi %265 : i32 to i128
      %268 = arith.extsi %266 : i32 to i64
      %269 = llvm.getelementptr %arg3[%268] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %267, %269 : i128, !llvm.ptr
      %270 = arith.constant 0 : i32
      %271 = arith.constant 0 : i32
      %272 = arith.extsi %270 : i32 to i128
      %273 = arith.extsi %271 : i32 to i64
      %274 = llvm.getelementptr %arg4[%273] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %272, %274 : i128, !llvm.ptr
      %275 = arith.constant 0 : i32
      %276 = arith.extsi %275 : i32 to i128
      func.return %276 : i128
    ^bb61:
      cf.br ^bb62
    ^bb62:
    %277 = arith.constant 4 : i32
    %279 = arith.extsi %277 : i32 to i64
    %278 = arith.muli %279, %arg0 : i64
    %280 = arith.constant 2 : i32
    %282 = arith.extsi %280 : i32 to i64
    %281 = arith.addi %278, %282 : i64
    %283 = arith.extsi %281 : i64 to i128
    %284 = arith.constant 0 : i32
    %285 = arith.extsi %284 : i32 to i128
    %286 = llvm.mlir.constant(1 : i64) : i64
    %287 = llvm.alloca %286 x i128 : (i64) -> !llvm.ptr
    llvm.store %285, %287 : i128, !llvm.ptr
    %288 = arith.constant 1 : i32
    %289 = arith.extsi %288 : i32 to i128
    %290 = llvm.mlir.constant(1 : i64) : i64
    %291 = llvm.alloca %290 x i128 : (i64) -> !llvm.ptr
    llvm.store %289, %291 : i128, !llvm.ptr
    %292 = arith.constant 0 : i32
    %293 = arith.extsi %292 : i32 to i128
    %294 = llvm.mlir.constant(1 : i64) : i64
    %295 = llvm.alloca %294 x i128 : (i64) -> !llvm.ptr
    llvm.store %293, %295 : i128, !llvm.ptr
    %296 = arith.constant 0 : i32
    %297 = arith.extsi %296 : i32 to i128
    %298 = llvm.mlir.constant(1 : i64) : i64
    %299 = llvm.alloca %298 x i128 : (i64) -> !llvm.ptr
    llvm.store %297, %299 : i128, !llvm.ptr
    %300 = arith.constant 0 : i32
    %301 = arith.cmpi eq, %arg1, %300 : i32
    cf.cond_br %301, ^bb63, ^bb64
    ^bb63:
      %302 = arith.constant 0 : i32
      %303 = arith.extsi %302 : i32 to i128
      llvm.store %303, %295 : i128, !llvm.ptr
      cf.br ^bb65
    ^bb64:
      %304 = arith.constant 1 : i32
      %305 = arith.cmpi eq, %arg1, %304 : i32
      cf.cond_br %305, ^bb66, ^bb67
      ^bb66:
        %306 = arith.constant 1 : i32
        %307 = arith.extsi %306 : i32 to i128
        llvm.store %307, %295 : i128, !llvm.ptr
        cf.br ^bb68
      ^bb67:
        %308 = arith.constant 0 : i32
        %309 = arith.extsi %308 : i32 to i128
        llvm.store %309, %295 : i128, !llvm.ptr
        cf.br ^bb68
      ^bb68:
      cf.br ^bb65
    ^bb65:
    %310 = arith.constant 0 : i32
    %311 = arith.cmpi eq, %arg2, %310 : i32
    cf.cond_br %311, ^bb69, ^bb70
    ^bb69:
      %312 = arith.constant 0 : i32
      %313 = arith.extsi %312 : i32 to i128
      llvm.store %313, %299 : i128, !llvm.ptr
      cf.br ^bb71
    ^bb70:
      %314 = arith.constant 1 : i32
      %315 = arith.cmpi eq, %arg2, %314 : i32
      cf.cond_br %315, ^bb72, ^bb73
      ^bb72:
        %316 = arith.constant 1 : i32
        %317 = arith.extsi %316 : i32 to i128
        llvm.store %317, %299 : i128, !llvm.ptr
        cf.br ^bb74
      ^bb73:
        %318 = arith.constant 0 : i32
        %319 = arith.extsi %318 : i32 to i128
        llvm.store %319, %299 : i128, !llvm.ptr
        cf.br ^bb74
      ^bb74:
      cf.br ^bb71
    ^bb71:
    %320 = arith.constant 2 : i32
    %321 = llvm.mlir.constant(1 : i64) : i64
    %322 = llvm.alloca %321 x i32 : (i64) -> !llvm.ptr
    llvm.store %320, %322 : i32, !llvm.ptr
    cf.br ^bb75
    ^bb75:
    %323 = llvm.load %322 : !llvm.ptr -> i32
    %324 = arith.cmpi sle, %323, %arg1 : i32
    %325 = scf.if %324 -> (i1) {
      %326 = arith.constant true
      scf.yield %326 : i1
    } else {
      %327 = llvm.load %322 : !llvm.ptr -> i32
      %328 = arith.cmpi sle, %327, %arg2 : i32
      scf.yield %328 : i1
    }
    cf.cond_br %325, ^bb76, ^bb77
    ^bb76:
      %330 = llvm.load %291 : !llvm.ptr -> i128
      %329 = func.call @mul_overflow(%283, %330) : (i128, i128) -> i128
      %331 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
      %332 = llvm.load %331 : !llvm.ptr -> i128
      %334 = arith.trunci %329 : i128 to i64
      %335 = arith.trunci %332 : i128 to i64
      %333 = arith.cmpi eq, %334, %335 : i64
      cf.cond_br %333, ^bb78, ^bb79
      ^bb78:
        %336 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
        %337 = llvm.load %336 : !llvm.ptr -> i128
        %338 = arith.constant 0 : i32
        %339 = arith.extsi %338 : i32 to i64
        %340 = llvm.getelementptr %arg3[%339] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %337, %340 : i128, !llvm.ptr
        %341 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
        %342 = llvm.load %341 : !llvm.ptr -> i128
        %343 = arith.constant 0 : i32
        %344 = arith.extsi %343 : i32 to i64
        %345 = llvm.getelementptr %arg4[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %342, %345 : i128, !llvm.ptr
        %346 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
        %347 = llvm.load %346 : !llvm.ptr -> i128
        func.return %347 : i128
      ^bb79:
        cf.br ^bb80
      ^bb80:
      %348 = llvm.load %287 : !llvm.ptr -> i128
      %350 = arith.trunci %329 : i128 to i64
      %351 = arith.trunci %348 : i128 to i64
      %349 = arith.subi %350, %351 : i64
      %352 = arith.extsi %349 : i64 to i128
      %353 = func.call @abs_i128(%352) : (i128) -> i128
      %354 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
      %355 = llvm.load %354 : !llvm.ptr -> i128
      %357 = arith.trunci %353 : i128 to i64
      %358 = arith.trunci %355 : i128 to i64
      %356 = arith.cmpi sgt, %357, %358 : i64
      cf.cond_br %356, ^bb81, ^bb82
      ^bb81:
        %359 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
        %360 = llvm.load %359 : !llvm.ptr -> i128
        %361 = arith.constant 0 : i32
        %362 = arith.extsi %361 : i32 to i64
        %363 = llvm.getelementptr %arg3[%362] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %360, %363 : i128, !llvm.ptr
        %364 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
        %365 = llvm.load %364 : !llvm.ptr -> i128
        %366 = arith.constant 0 : i32
        %367 = arith.extsi %366 : i32 to i64
        %368 = llvm.getelementptr %arg4[%367] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %365, %368 : i128, !llvm.ptr
        %369 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
        %370 = llvm.load %369 : !llvm.ptr -> i128
        func.return %370 : i128
      ^bb82:
        cf.br ^bb83
      ^bb83:
      %371 = llvm.load %291 : !llvm.ptr -> i128
      llvm.store %371, %287 : i128, !llvm.ptr
      llvm.store %352, %291 : i128, !llvm.ptr
      %372 = llvm.load %322 : !llvm.ptr -> i32
      %373 = arith.cmpi eq, %372, %arg1 : i32
      cf.cond_br %373, ^bb84, ^bb85
      ^bb84:
        %374 = llvm.load %291 : !llvm.ptr -> i128
        llvm.store %374, %295 : i128, !llvm.ptr
        cf.br ^bb86
      ^bb85:
        cf.br ^bb86
      ^bb86:
      %375 = llvm.load %322 : !llvm.ptr -> i32
      %376 = arith.cmpi eq, %375, %arg2 : i32
      cf.cond_br %376, ^bb87, ^bb88
      ^bb87:
        %377 = llvm.load %291 : !llvm.ptr -> i128
        llvm.store %377, %299 : i128, !llvm.ptr
        cf.br ^bb89
      ^bb88:
        cf.br ^bb89
      ^bb89:
      %378 = llvm.load %322 : !llvm.ptr -> i32
      %379 = arith.constant 1 : i32
      %380 = arith.addi %378, %379 : i32
      llvm.store %380, %322 : i32, !llvm.ptr
      cf.br ^bb75
    ^bb77:
    %381 = llvm.load %295 : !llvm.ptr -> i128
    %382 = arith.constant 0 : i32
    %383 = arith.extsi %382 : i32 to i64
    %384 = llvm.getelementptr %arg3[%383] : (!llvm.ptr, i64) -> !llvm.ptr, i128
    llvm.store %381, %384 : i128, !llvm.ptr
    %385 = llvm.load %299 : !llvm.ptr -> i128
    %386 = arith.constant 0 : i32
    %387 = arith.extsi %386 : i32 to i64
    %388 = llvm.getelementptr %arg4[%387] : (!llvm.ptr, i64) -> !llvm.ptr, i128
    llvm.store %385, %388 : i128, !llvm.ptr
    %389 = arith.extsi %arg0 : i64 to i128
    %390 = arith.constant 1 : i32
    %392 = arith.extsi %390 : i32 to i64
    %391 = arith.addi %arg0, %392 : i64
    %393 = arith.extsi %391 : i64 to i128
    %395 = arith.trunci %389 : i128 to i64
    %396 = arith.trunci %393 : i128 to i64
    %394 = arith.muli %395, %396 : i64
    %397 = arith.constant 2 : i32
    %399 = arith.extsi %397 : i32 to i64
    %398 = arith.divsi %394, %399 : i64
    %400 = arith.extsi %398 : i64 to i128
    %402 = llvm.load %295 : !llvm.ptr -> i128
    %401 = func.call @mul_overflow(%400, %402) : (i128, i128) -> i128
    %403 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
    %404 = llvm.load %403 : !llvm.ptr -> i128
    %406 = arith.trunci %401 : i128 to i64
    %407 = arith.trunci %404 : i128 to i64
    %405 = arith.cmpi eq, %406, %407 : i64
    cf.cond_br %405, ^bb90, ^bb91
    ^bb90:
      %408 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
      %409 = llvm.load %408 : !llvm.ptr -> i128
      func.return %409 : i128
    ^bb91:
      cf.br ^bb92
    ^bb92:
    %411 = llvm.load %299 : !llvm.ptr -> i128
    %410 = func.call @mul_overflow(%401, %411) : (i128, i128) -> i128
    %412 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
    %413 = llvm.load %412 : !llvm.ptr -> i128
    %415 = arith.trunci %410 : i128 to i64
    %416 = arith.trunci %413 : i128 to i64
    %414 = arith.cmpi eq, %415, %416 : i64
    cf.cond_br %414, ^bb93, ^bb94
    ^bb93:
      %417 = llvm.mlir.addressof @I128_CAP : !llvm.ptr
      %418 = llvm.load %417 : !llvm.ptr -> i128
      func.return %418 : i128
    ^bb94:
      cf.br ^bb95
    ^bb95:
    func.return %410 : i128
  }
  func.func @get_N_i128() -> i128 {
    %419 = arith.constant 99999995705032704 : i32
    %420 = arith.extsi %419 : i32 to i128
    %421 = arith.constant 999999995705032704 : i32
    %422 = arith.extsi %421 : i32 to i128
    %424 = arith.trunci %420 : i128 to i64
    %425 = arith.trunci %422 : i128 to i64
    %423 = arith.muli %424, %425 : i64
    %426 = arith.extsi %423 : i64 to i128
    func.return %426 : i128
  }
  func.func @max_n_for_pair(%arg0: i32, %arg1: i32) -> i64 {
    %427 = func.call @get_N_i128() : () -> i128
    %429 = arith.constant 2 : i32
    %430 = arith.constant 16 : i32
    %431 = arith.extsi %429 : i32 to i64
    %432 = arith.extsi %430 : i32 to i64
    %428 = func.call @calloc(%431, %432) : (i64, i64) -> !llvm.ptr
    %434 = arith.constant 2 : i32
    %435 = arith.constant 16 : i32
    %436 = arith.extsi %434 : i32 to i64
    %437 = arith.extsi %435 : i32 to i64
    %433 = func.call @calloc(%436, %437) : (i64, i64) -> !llvm.ptr
    %439 = arith.constant 1 : i32
    %440 = arith.extsi %439 : i32 to i64
    %438 = func.call @c_value_i128(%440, %arg0, %arg1, %428, %433) : (i64, i32, i32, !llvm.ptr, !llvm.ptr) -> i128
    %442 = arith.trunci %438 : i128 to i64
    %443 = arith.trunci %427 : i128 to i64
    %441 = arith.cmpi sgt, %442, %443 : i64
    cf.cond_br %441, ^bb96, ^bb97
    ^bb96:
      func.call @free(%428) : (!llvm.ptr) -> ()
      func.call @free(%433) : (!llvm.ptr) -> ()
      %446 = arith.constant 0 : i32
      %447 = arith.extsi %446 : i32 to i64
      func.return %447 : i64
    ^bb97:
      cf.br ^bb98
    ^bb98:
    %448 = arith.constant 2 : i32
    %449 = arith.extsi %448 : i32 to i64
    %450 = llvm.mlir.constant(1 : i64) : i64
    %451 = llvm.alloca %450 x i64 : (i64) -> !llvm.ptr
    llvm.store %449, %451 : i64, !llvm.ptr
    cf.br ^bb99
    ^bb99:
    %453 = llvm.load %451 : !llvm.ptr -> i64
    %452 = func.call @log_c_value(%453, %arg0, %arg1) : (i64, i32, i32) -> f64
    %454 = llvm.mlir.addressof @LOG10_35 : !llvm.ptr
    %455 = llvm.load %454 : !llvm.ptr -> f64
    %456 = arith.cmpf olt, %452, %455 : f64
    cf.cond_br %456, ^bb100, ^bb101
    ^bb100:
      %457 = llvm.load %451 : !llvm.ptr -> i64
      %458 = arith.constant 2 : i32
      %460 = arith.extsi %458 : i32 to i64
      %459 = arith.muli %457, %460 : i64
      llvm.store %459, %451 : i64, !llvm.ptr
      %461 = llvm.load %451 : !llvm.ptr -> i64
      %462 = arith.constant 9995705032704 : i32
      %464 = arith.extsi %462 : i32 to i64
      %463 = arith.cmpi sgt, %461, %464 : i64
      cf.cond_br %463, ^bb102, ^bb103
      ^bb102:
        %465 = arith.constant 9995705032704 : i32
        %466 = arith.extsi %465 : i32 to i64
        llvm.store %466, %451 : i64, !llvm.ptr
        cf.br ^bb101
      ^bb103:
        cf.br ^bb104
      ^bb104:
      cf.br ^bb99
    ^bb101:
    %467 = arith.constant 1 : i32
    %468 = arith.extsi %467 : i32 to i64
    %469 = llvm.mlir.constant(1 : i64) : i64
    %470 = llvm.alloca %469 x i64 : (i64) -> !llvm.ptr
    llvm.store %468, %470 : i64, !llvm.ptr
    cf.br ^bb105
    ^bb105:
    %471 = llvm.load %470 : !llvm.ptr -> i64
    %472 = arith.constant 1 : i32
    %474 = arith.extsi %472 : i32 to i64
    %473 = arith.addi %471, %474 : i64
    %475 = llvm.load %451 : !llvm.ptr -> i64
    %476 = arith.cmpi slt, %473, %475 : i64
    cf.cond_br %476, ^bb106, ^bb107
    ^bb106:
      %477 = llvm.load %470 : !llvm.ptr -> i64
      %478 = llvm.load %451 : !llvm.ptr -> i64
      %479 = arith.addi %477, %478 : i64
      %480 = arith.constant 2 : i32
      %482 = arith.extsi %480 : i32 to i64
      %481 = arith.divsi %479, %482 : i64
      %483 = func.call @c_value_i128(%481, %arg0, %arg1, %428, %433) : (i64, i32, i32, !llvm.ptr, !llvm.ptr) -> i128
      %485 = arith.trunci %483 : i128 to i64
      %486 = arith.trunci %427 : i128 to i64
      %484 = arith.cmpi sle, %485, %486 : i64
      cf.cond_br %484, ^bb108, ^bb109
      ^bb108:
        llvm.store %481, %470 : i64, !llvm.ptr
        cf.br ^bb110
      ^bb109:
        llvm.store %481, %451 : i64, !llvm.ptr
        cf.br ^bb110
      ^bb110:
      cf.br ^bb105
    ^bb107:
    %488 = llvm.load %470 : !llvm.ptr -> i64
    %487 = func.call @c_value_i128(%488, %arg0, %arg1, %428, %433) : (i64, i32, i32, !llvm.ptr, !llvm.ptr) -> i128
    %490 = arith.trunci %487 : i128 to i64
    %491 = arith.trunci %427 : i128 to i64
    %489 = arith.cmpi sle, %490, %491 : i64
    %492 = scf.if %489 -> (i64) {
      %493 = llvm.load %470 : !llvm.ptr -> i64
      scf.yield %493 : i64
    } else {
      %494 = llvm.load %470 : !llvm.ptr -> i64
      %495 = arith.constant 1 : i32
      %497 = arith.extsi %495 : i32 to i64
      %496 = arith.subi %494, %497 : i64
      scf.yield %496 : i64
    }
    func.call @free(%428) : (!llvm.ptr) -> ()
    func.call @free(%433) : (!llvm.ptr) -> ()
    func.return %492 : i64
  }
  func.func @binom_mod(%arg0: i64, %arg1: i32) -> i64 {
    %500 = arith.constant 0 : i32
    %501 = arith.cmpi slt, %arg1, %500 : i32
    cf.cond_br %501, ^bb111, ^bb112
    ^bb111:
      %502 = arith.constant 0 : i32
      %503 = arith.extsi %502 : i32 to i64
      func.return %503 : i64
    ^bb112:
      cf.br ^bb113
    ^bb113:
    %504 = arith.constant 0 : i32
    %505 = arith.cmpi eq, %arg1, %504 : i32
    cf.cond_br %505, ^bb114, ^bb115
    ^bb114:
      %506 = arith.constant 1 : i32
      %507 = llvm.mlir.addressof @MOD : !llvm.ptr
      %508 = llvm.load %507 : !llvm.ptr -> i64
      %510 = arith.extsi %506 : i32 to i64
      %509 = arith.remsi %510, %508 : i64
      func.return %509 : i64
    ^bb115:
      cf.br ^bb116
    ^bb116:
    %511 = llvm.mlir.addressof @MOD : !llvm.ptr
    %512 = llvm.load %511 : !llvm.ptr -> i64
    %513 = arith.remsi %arg0, %512 : i64
    %514 = arith.constant 0 : i32
    %516 = arith.extsi %514 : i32 to i64
    %515 = arith.cmpi slt, %513, %516 : i64
    %517 = scf.if %515 -> (i64) {
      %518 = llvm.mlir.addressof @MOD : !llvm.ptr
      %519 = llvm.load %518 : !llvm.ptr -> i64
      %520 = arith.addi %513, %519 : i64
      scf.yield %520 : i64
    } else {
      scf.yield %513 : i64
    }
    %521 = arith.constant 1 : i32
    %522 = arith.extsi %521 : i32 to i64
    %523 = llvm.mlir.constant(1 : i64) : i64
    %524 = llvm.alloca %523 x i64 : (i64) -> !llvm.ptr
    llvm.store %522, %524 : i64, !llvm.ptr
    %525 = arith.constant 0 : i32
    %526 = llvm.mlir.constant(1 : i64) : i64
    %527 = llvm.alloca %526 x i32 : (i64) -> !llvm.ptr
    llvm.store %525, %527 : i32, !llvm.ptr
    cf.br ^bb117
    ^bb117:
    %528 = llvm.load %527 : !llvm.ptr -> i32
    %529 = arith.cmpi slt, %528, %arg1 : i32
    cf.cond_br %529, ^bb118, ^bb119
    ^bb118:
      %530 = llvm.load %527 : !llvm.ptr -> i32
      %531 = arith.extsi %530 : i32 to i64
      %532 = arith.subi %517, %531 : i64
      %533 = llvm.mlir.addressof @MOD : !llvm.ptr
      %534 = llvm.load %533 : !llvm.ptr -> i64
      %535 = arith.remsi %532, %534 : i64
      %536 = arith.constant 0 : i32
      %538 = arith.extsi %536 : i32 to i64
      %537 = arith.cmpi slt, %535, %538 : i64
      %539 = scf.if %537 -> (i64) {
        %540 = llvm.mlir.addressof @MOD : !llvm.ptr
        %541 = llvm.load %540 : !llvm.ptr -> i64
        %542 = arith.addi %535, %541 : i64
        scf.yield %542 : i64
      } else {
        scf.yield %535 : i64
      }
      %543 = llvm.load %524 : !llvm.ptr -> i64
      %544 = arith.muli %543, %539 : i64
      %545 = llvm.mlir.addressof @MOD : !llvm.ptr
      %546 = llvm.load %545 : !llvm.ptr -> i64
      %547 = arith.remsi %544, %546 : i64
      llvm.store %547, %524 : i64, !llvm.ptr
      %548 = llvm.load %527 : !llvm.ptr -> i32
      %549 = arith.constant 1 : i32
      %550 = arith.addi %548, %549 : i32
      llvm.store %550, %527 : i32, !llvm.ptr
      cf.br ^bb117
    ^bb119:
    %551 = arith.constant 1 : i32
    %552 = arith.extsi %551 : i32 to i64
    %553 = llvm.mlir.constant(1 : i64) : i64
    %554 = llvm.alloca %553 x i64 : (i64) -> !llvm.ptr
    llvm.store %552, %554 : i64, !llvm.ptr
    %555 = arith.constant 1 : i32
    %556 = llvm.mlir.constant(1 : i64) : i64
    %557 = llvm.alloca %556 x i32 : (i64) -> !llvm.ptr
    llvm.store %555, %557 : i32, !llvm.ptr
    cf.br ^bb120
    ^bb120:
    %558 = llvm.load %557 : !llvm.ptr -> i32
    %559 = arith.cmpi sle, %558, %arg1 : i32
    cf.cond_br %559, ^bb121, ^bb122
    ^bb121:
      %560 = llvm.load %554 : !llvm.ptr -> i64
      %561 = llvm.load %557 : !llvm.ptr -> i32
      %562 = arith.extsi %561 : i32 to i64
      %563 = arith.muli %560, %562 : i64
      %564 = llvm.mlir.addressof @MOD : !llvm.ptr
      %565 = llvm.load %564 : !llvm.ptr -> i64
      %566 = arith.remsi %563, %565 : i64
      llvm.store %566, %554 : i64, !llvm.ptr
      %567 = llvm.load %557 : !llvm.ptr -> i32
      %568 = arith.constant 1 : i32
      %569 = arith.addi %567, %568 : i32
      llvm.store %569, %557 : i32, !llvm.ptr
      cf.br ^bb120
    ^bb122:
    %570 = llvm.load %524 : !llvm.ptr -> i64
    %572 = llvm.load %554 : !llvm.ptr -> i64
    %573 = llvm.mlir.addressof @MOD : !llvm.ptr
    %574 = llvm.load %573 : !llvm.ptr -> i64
    %571 = func.call @mod_inv(%572, %574) : (i64, i64) -> i64
    %575 = arith.muli %570, %571 : i64
    %576 = llvm.mlir.addressof @MOD : !llvm.ptr
    %577 = llvm.load %576 : !llvm.ptr -> i64
    %578 = arith.remsi %575, %577 : i64
    func.return %578 : i64
  }
  func.func @sum_for_pair(%arg0: i32, %arg1: i32, %arg2: i64) -> i64 {
    %579 = arith.addi %arg0, %arg1 : i32
    %581 = arith.constant 1 : i32
    %582 = arith.addi %579, %581 : i32
    %583 = arith.extsi %582 : i32 to i64
    %584 = arith.constant 8 : i32
    %585 = arith.extsi %584 : i32 to i64
    %580 = func.call @calloc(%583, %585) : (i64, i64) -> !llvm.ptr
    %586 = arith.constant 0 : i32
    %587 = arith.extsi %586 : i32 to i64
    %588 = llvm.mlir.constant(1 : i64) : i64
    %589 = llvm.alloca %588 x i64 : (i64) -> !llvm.ptr
    llvm.store %587, %589 : i64, !llvm.ptr
    cf.br ^bb123
    ^bb123:
    %590 = llvm.load %589 : !llvm.ptr -> i64
    %591 = arith.extsi %579 : i32 to i64
    %592 = arith.cmpi sle, %590, %591 : i64
    cf.cond_br %592, ^bb124, ^bb125
    ^bb124:
      %593 = arith.constant 4 : i32
      %594 = llvm.load %589 : !llvm.ptr -> i64
      %596 = arith.extsi %593 : i32 to i64
      %595 = arith.muli %596, %594 : i64
      %597 = arith.constant 2 : i32
      %599 = arith.extsi %597 : i32 to i64
      %598 = arith.addi %595, %599 : i64
      %600 = llvm.mlir.addressof @MOD : !llvm.ptr
      %601 = llvm.load %600 : !llvm.ptr -> i64
      %602 = arith.remsi %598, %601 : i64
      %603 = arith.constant 0 : i32
      %605 = arith.extsi %603 : i32 to i64
      %604 = arith.cmpi slt, %602, %605 : i64
      %606 = scf.if %604 -> (i64) {
        %607 = llvm.mlir.addressof @MOD : !llvm.ptr
        %608 = llvm.load %607 : !llvm.ptr -> i64
        %609 = arith.addi %602, %608 : i64
        scf.yield %609 : i64
      } else {
        scf.yield %602 : i64
      }
      %610 = arith.constant 0 : i32
      %611 = arith.extsi %610 : i32 to i64
      %612 = llvm.mlir.constant(1 : i64) : i64
      %613 = llvm.alloca %612 x i64 : (i64) -> !llvm.ptr
      llvm.store %611, %613 : i64, !llvm.ptr
      %614 = arith.constant 1 : i32
      %615 = llvm.mlir.addressof @MOD : !llvm.ptr
      %616 = llvm.load %615 : !llvm.ptr -> i64
      %618 = arith.extsi %614 : i32 to i64
      %617 = arith.remsi %618, %616 : i64
      %619 = llvm.mlir.constant(1 : i64) : i64
      %620 = llvm.alloca %619 x i64 : (i64) -> !llvm.ptr
      llvm.store %617, %620 : i64, !llvm.ptr
      %621 = arith.constant 0 : i32
      %622 = arith.extsi %621 : i32 to i64
      %623 = llvm.mlir.constant(1 : i64) : i64
      %624 = llvm.alloca %623 x i64 : (i64) -> !llvm.ptr
      llvm.store %622, %624 : i64, !llvm.ptr
      %625 = arith.constant 0 : i32
      %626 = arith.extsi %625 : i32 to i64
      %627 = llvm.mlir.constant(1 : i64) : i64
      %628 = llvm.alloca %627 x i64 : (i64) -> !llvm.ptr
      llvm.store %626, %628 : i64, !llvm.ptr
      %629 = arith.constant 0 : i32
      %630 = arith.cmpi eq, %arg0, %629 : i32
      cf.cond_br %630, ^bb126, ^bb127
      ^bb126:
        %631 = arith.constant 0 : i32
        %632 = arith.extsi %631 : i32 to i64
        llvm.store %632, %624 : i64, !llvm.ptr
        cf.br ^bb128
      ^bb127:
        %633 = arith.constant 1 : i32
        %634 = arith.cmpi eq, %arg0, %633 : i32
        cf.cond_br %634, ^bb129, ^bb130
        ^bb129:
          %635 = arith.constant 1 : i32
          %636 = llvm.mlir.addressof @MOD : !llvm.ptr
          %637 = llvm.load %636 : !llvm.ptr -> i64
          %639 = arith.extsi %635 : i32 to i64
          %638 = arith.remsi %639, %637 : i64
          llvm.store %638, %624 : i64, !llvm.ptr
          cf.br ^bb131
        ^bb130:
          %640 = arith.constant 0 : i32
          %641 = arith.extsi %640 : i32 to i64
          llvm.store %641, %624 : i64, !llvm.ptr
          cf.br ^bb131
        ^bb131:
        cf.br ^bb128
      ^bb128:
      %642 = arith.constant 0 : i32
      %643 = arith.cmpi eq, %arg1, %642 : i32
      cf.cond_br %643, ^bb132, ^bb133
      ^bb132:
        %644 = arith.constant 0 : i32
        %645 = arith.extsi %644 : i32 to i64
        llvm.store %645, %628 : i64, !llvm.ptr
        cf.br ^bb134
      ^bb133:
        %646 = arith.constant 1 : i32
        %647 = arith.cmpi eq, %arg1, %646 : i32
        cf.cond_br %647, ^bb135, ^bb136
        ^bb135:
          %648 = arith.constant 1 : i32
          %649 = llvm.mlir.addressof @MOD : !llvm.ptr
          %650 = llvm.load %649 : !llvm.ptr -> i64
          %652 = arith.extsi %648 : i32 to i64
          %651 = arith.remsi %652, %650 : i64
          llvm.store %651, %628 : i64, !llvm.ptr
          cf.br ^bb137
        ^bb136:
          %653 = arith.constant 0 : i32
          %654 = arith.extsi %653 : i32 to i64
          llvm.store %654, %628 : i64, !llvm.ptr
          cf.br ^bb137
        ^bb137:
        cf.br ^bb134
      ^bb134:
      %655 = arith.constant 2 : i32
      %656 = llvm.mlir.constant(1 : i64) : i64
      %657 = llvm.alloca %656 x i32 : (i64) -> !llvm.ptr
      llvm.store %655, %657 : i32, !llvm.ptr
      cf.br ^bb138
      ^bb138:
      %658 = llvm.load %657 : !llvm.ptr -> i32
      %659 = arith.cmpi sle, %658, %arg0 : i32
      %660 = scf.if %659 -> (i1) {
        %661 = arith.constant true
        scf.yield %661 : i1
      } else {
        %662 = llvm.load %657 : !llvm.ptr -> i32
        %663 = arith.cmpi sle, %662, %arg1 : i32
        scf.yield %663 : i1
      }
      cf.cond_br %660, ^bb139, ^bb140
      ^bb139:
        %664 = llvm.load %620 : !llvm.ptr -> i64
        %665 = arith.muli %606, %664 : i64
        %666 = llvm.mlir.addressof @MOD : !llvm.ptr
        %667 = llvm.load %666 : !llvm.ptr -> i64
        %668 = arith.remsi %665, %667 : i64
        %669 = llvm.load %613 : !llvm.ptr -> i64
        %670 = llvm.mlir.addressof @MOD : !llvm.ptr
        %671 = llvm.load %670 : !llvm.ptr -> i64
        %672 = arith.remsi %669, %671 : i64
        %673 = arith.subi %668, %672 : i64
        %674 = llvm.mlir.addressof @MOD : !llvm.ptr
        %675 = llvm.load %674 : !llvm.ptr -> i64
        %676 = arith.addi %673, %675 : i64
        %677 = llvm.mlir.addressof @MOD : !llvm.ptr
        %678 = llvm.load %677 : !llvm.ptr -> i64
        %679 = arith.remsi %676, %678 : i64
        %680 = llvm.load %620 : !llvm.ptr -> i64
        llvm.store %680, %613 : i64, !llvm.ptr
        llvm.store %679, %620 : i64, !llvm.ptr
        %681 = llvm.load %657 : !llvm.ptr -> i32
        %682 = arith.cmpi eq, %681, %arg0 : i32
        cf.cond_br %682, ^bb141, ^bb142
        ^bb141:
          %683 = llvm.load %620 : !llvm.ptr -> i64
          llvm.store %683, %624 : i64, !llvm.ptr
          cf.br ^bb143
        ^bb142:
          cf.br ^bb143
        ^bb143:
        %684 = llvm.load %657 : !llvm.ptr -> i32
        %685 = arith.cmpi eq, %684, %arg1 : i32
        cf.cond_br %685, ^bb144, ^bb145
        ^bb144:
          %686 = llvm.load %620 : !llvm.ptr -> i64
          llvm.store %686, %628 : i64, !llvm.ptr
          cf.br ^bb146
        ^bb145:
          cf.br ^bb146
        ^bb146:
        %687 = llvm.load %657 : !llvm.ptr -> i32
        %688 = arith.constant 1 : i32
        %689 = arith.addi %687, %688 : i32
        llvm.store %689, %657 : i32, !llvm.ptr
        cf.br ^bb138
      ^bb140:
      %690 = llvm.load %589 : !llvm.ptr -> i64
      %691 = llvm.mlir.addressof @MOD : !llvm.ptr
      %692 = llvm.load %691 : !llvm.ptr -> i64
      %693 = arith.remsi %690, %692 : i64
      %694 = llvm.load %589 : !llvm.ptr -> i64
      %695 = arith.constant 1 : i32
      %697 = arith.extsi %695 : i32 to i64
      %696 = arith.addi %694, %697 : i64
      %698 = llvm.mlir.addressof @MOD : !llvm.ptr
      %699 = llvm.load %698 : !llvm.ptr -> i64
      %700 = arith.remsi %696, %699 : i64
      %701 = arith.muli %693, %700 : i64
      %702 = llvm.mlir.addressof @MOD : !llvm.ptr
      %703 = llvm.load %702 : !llvm.ptr -> i64
      %704 = arith.remsi %701, %703 : i64
      %706 = arith.constant 2 : i32
      %707 = llvm.mlir.addressof @MOD : !llvm.ptr
      %708 = llvm.load %707 : !llvm.ptr -> i64
      %709 = arith.extsi %706 : i32 to i64
      %705 = func.call @mod_inv(%709, %708) : (i64, i64) -> i64
      %710 = arith.muli %704, %705 : i64
      %711 = llvm.mlir.addressof @MOD : !llvm.ptr
      %712 = llvm.load %711 : !llvm.ptr -> i64
      %713 = arith.remsi %710, %712 : i64
      %714 = llvm.load %624 : !llvm.ptr -> i64
      %715 = arith.muli %713, %714 : i64
      %716 = llvm.mlir.addressof @MOD : !llvm.ptr
      %717 = llvm.load %716 : !llvm.ptr -> i64
      %718 = arith.remsi %715, %717 : i64
      %719 = llvm.load %628 : !llvm.ptr -> i64
      %720 = arith.muli %718, %719 : i64
      %721 = llvm.mlir.addressof @MOD : !llvm.ptr
      %722 = llvm.load %721 : !llvm.ptr -> i64
      %723 = arith.remsi %720, %722 : i64
      %724 = llvm.load %589 : !llvm.ptr -> i64
      %725 = llvm.getelementptr %580[%724] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %723, %725 : i64, !llvm.ptr
      %726 = llvm.load %589 : !llvm.ptr -> i64
      %727 = arith.constant 1 : i32
      %729 = arith.extsi %727 : i32 to i64
      %728 = arith.addi %726, %729 : i64
      llvm.store %728, %589 : i64, !llvm.ptr
      cf.br ^bb123
    ^bb125:
    %731 = arith.constant 1 : i32
    %732 = arith.addi %579, %731 : i32
    %733 = arith.extsi %732 : i32 to i64
    %734 = arith.constant 8 : i32
    %735 = arith.extsi %734 : i32 to i64
    %730 = func.call @calloc(%733, %735) : (i64, i64) -> !llvm.ptr
    %737 = arith.constant 1 : i32
    %738 = arith.addi %579, %737 : i32
    %739 = arith.extsi %738 : i32 to i64
    %740 = arith.constant 8 : i32
    %741 = arith.extsi %740 : i32 to i64
    %736 = func.call @calloc(%739, %741) : (i64, i64) -> !llvm.ptr
    %742 = arith.constant 0 : i32
    %743 = arith.extsi %742 : i32 to i64
    %744 = llvm.mlir.constant(1 : i64) : i64
    %745 = llvm.alloca %744 x i64 : (i64) -> !llvm.ptr
    llvm.store %743, %745 : i64, !llvm.ptr
    cf.br ^bb147
    ^bb147:
    %746 = llvm.load %745 : !llvm.ptr -> i64
    %747 = arith.extsi %579 : i32 to i64
    %748 = arith.cmpi sle, %746, %747 : i64
    cf.cond_br %748, ^bb148, ^bb149
    ^bb148:
      %750 = llvm.load %745 : !llvm.ptr -> i64
      %751 = llvm.getelementptr %580[%750] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %749 = llvm.load %751 : !llvm.ptr -> i64
      %752 = llvm.load %745 : !llvm.ptr -> i64
      %753 = llvm.getelementptr %736[%752] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %749, %753 : i64, !llvm.ptr
      %754 = llvm.load %745 : !llvm.ptr -> i64
      %755 = arith.constant 1 : i32
      %757 = arith.extsi %755 : i32 to i64
      %756 = arith.addi %754, %757 : i64
      llvm.store %756, %745 : i64, !llvm.ptr
      cf.br ^bb147
    ^bb149:
    %758 = arith.constant 1 : i32
    %759 = arith.addi %579, %758 : i32
    %760 = llvm.mlir.constant(1 : i64) : i64
    %761 = llvm.alloca %760 x i32 : (i64) -> !llvm.ptr
    llvm.store %759, %761 : i32, !llvm.ptr
    %762 = arith.constant 0 : i32
    %763 = llvm.mlir.constant(1 : i64) : i64
    %764 = llvm.alloca %763 x i32 : (i64) -> !llvm.ptr
    llvm.store %762, %764 : i32, !llvm.ptr
    cf.br ^bb150
    ^bb150:
    %765 = llvm.load %761 : !llvm.ptr -> i32
    %766 = arith.constant 0 : i32
    %767 = arith.cmpi sgt, %765, %766 : i32
    cf.cond_br %767, ^bb151, ^bb152
    ^bb151:
      %769 = arith.constant 0 : i32
      %770 = arith.extsi %769 : i32 to i64
      %771 = llvm.getelementptr %736[%770] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %768 = llvm.load %771 : !llvm.ptr -> i64
      %772 = llvm.load %764 : !llvm.ptr -> i32
      %773 = arith.extsi %772 : i32 to i64
      %774 = llvm.getelementptr %730[%773] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %768, %774 : i64, !llvm.ptr
      %775 = llvm.load %764 : !llvm.ptr -> i32
      %776 = arith.constant 1 : i32
      %777 = arith.addi %775, %776 : i32
      llvm.store %777, %764 : i32, !llvm.ptr
      %778 = arith.constant 0 : i32
      %779 = llvm.mlir.constant(1 : i64) : i64
      %780 = llvm.alloca %779 x i32 : (i64) -> !llvm.ptr
      llvm.store %778, %780 : i32, !llvm.ptr
      cf.br ^bb153
      ^bb153:
      %781 = llvm.load %780 : !llvm.ptr -> i32
      %782 = llvm.load %761 : !llvm.ptr -> i32
      %783 = arith.constant 1 : i32
      %784 = arith.subi %782, %783 : i32
      %785 = arith.cmpi slt, %781, %784 : i32
      cf.cond_br %785, ^bb154, ^bb155
      ^bb154:
        %787 = llvm.load %780 : !llvm.ptr -> i32
        %788 = arith.constant 1 : i32
        %789 = arith.addi %787, %788 : i32
        %790 = arith.extsi %789 : i32 to i64
        %791 = llvm.getelementptr %736[%790] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %786 = llvm.load %791 : !llvm.ptr -> i64
        %793 = llvm.load %780 : !llvm.ptr -> i32
        %794 = arith.extsi %793 : i32 to i64
        %795 = llvm.getelementptr %736[%794] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %792 = llvm.load %795 : !llvm.ptr -> i64
        %796 = llvm.mlir.addressof @MOD : !llvm.ptr
        %797 = llvm.load %796 : !llvm.ptr -> i64
        %798 = arith.remsi %792, %797 : i64
        %799 = arith.subi %786, %798 : i64
        %800 = llvm.mlir.addressof @MOD : !llvm.ptr
        %801 = llvm.load %800 : !llvm.ptr -> i64
        %802 = arith.addi %799, %801 : i64
        %803 = llvm.mlir.addressof @MOD : !llvm.ptr
        %804 = llvm.load %803 : !llvm.ptr -> i64
        %805 = arith.remsi %802, %804 : i64
        %806 = llvm.load %780 : !llvm.ptr -> i32
        %807 = arith.extsi %806 : i32 to i64
        %808 = llvm.getelementptr %736[%807] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %805, %808 : i64, !llvm.ptr
        %809 = llvm.load %780 : !llvm.ptr -> i32
        %810 = arith.constant 1 : i32
        %811 = arith.addi %809, %810 : i32
        llvm.store %811, %780 : i32, !llvm.ptr
        cf.br ^bb153
      ^bb155:
      %812 = llvm.load %761 : !llvm.ptr -> i32
      %813 = arith.constant 1 : i32
      %814 = arith.subi %812, %813 : i32
      llvm.store %814, %761 : i32, !llvm.ptr
      cf.br ^bb150
    ^bb152:
    %815 = arith.constant 0 : i32
    %816 = arith.extsi %815 : i32 to i64
    %817 = llvm.mlir.constant(1 : i64) : i64
    %818 = llvm.alloca %817 x i64 : (i64) -> !llvm.ptr
    llvm.store %816, %818 : i64, !llvm.ptr
    %819 = arith.constant 1 : i32
    %821 = arith.extsi %819 : i32 to i64
    %820 = arith.addi %arg2, %821 : i64
    %822 = arith.constant 0 : i32
    %823 = llvm.mlir.constant(1 : i64) : i64
    %824 = llvm.alloca %823 x i32 : (i64) -> !llvm.ptr
    llvm.store %822, %824 : i32, !llvm.ptr
    cf.br ^bb156
    ^bb156:
    %825 = llvm.load %824 : !llvm.ptr -> i32
    %826 = arith.cmpi sle, %825, %579 : i32
    cf.cond_br %826, ^bb157, ^bb158
    ^bb157:
      %828 = llvm.load %824 : !llvm.ptr -> i32
      %829 = arith.constant 1 : i32
      %830 = arith.addi %828, %829 : i32
      %827 = func.call @binom_mod(%820, %830) : (i64, i32) -> i64
      %832 = llvm.load %824 : !llvm.ptr -> i32
      %833 = arith.extsi %832 : i32 to i64
      %834 = llvm.getelementptr %730[%833] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %831 = llvm.load %834 : !llvm.ptr -> i64
      %835 = llvm.mlir.addressof @MOD : !llvm.ptr
      %836 = llvm.load %835 : !llvm.ptr -> i64
      %837 = arith.remsi %831, %836 : i64
      %838 = arith.muli %837, %827 : i64
      %839 = llvm.mlir.addressof @MOD : !llvm.ptr
      %840 = llvm.load %839 : !llvm.ptr -> i64
      %841 = arith.remsi %838, %840 : i64
      %842 = llvm.load %818 : !llvm.ptr -> i64
      %843 = arith.addi %842, %841 : i64
      %844 = llvm.mlir.addressof @MOD : !llvm.ptr
      %845 = llvm.load %844 : !llvm.ptr -> i64
      %846 = arith.remsi %843, %845 : i64
      llvm.store %846, %818 : i64, !llvm.ptr
      %847 = llvm.load %824 : !llvm.ptr -> i32
      %848 = arith.constant 1 : i32
      %849 = arith.addi %847, %848 : i32
      llvm.store %849, %824 : i32, !llvm.ptr
      cf.br ^bb156
    ^bb158:
    func.call @free(%580) : (!llvm.ptr) -> ()
    func.call @free(%730) : (!llvm.ptr) -> ()
    func.call @free(%736) : (!llvm.ptr) -> ()
    %853 = llvm.load %818 : !llvm.ptr -> i64
    func.return %853 : i64
  }
  func.func @maxJ_for_N() -> i32 {
    %854 = func.call @get_N_i128() : () -> i128
    %855 = arith.constant 6 : i32
    %856 = arith.extsi %855 : i32 to i128
    %857 = arith.constant 0 : i32
    %858 = arith.extsi %857 : i32 to i128
    %859 = llvm.mlir.constant(1 : i64) : i64
    %860 = llvm.alloca %859 x i128 : (i64) -> !llvm.ptr
    llvm.store %858, %860 : i128, !llvm.ptr
    %861 = arith.constant 1 : i32
    %862 = arith.extsi %861 : i32 to i128
    %863 = llvm.mlir.constant(1 : i64) : i64
    %864 = llvm.alloca %863 x i128 : (i64) -> !llvm.ptr
    llvm.store %862, %864 : i128, !llvm.ptr
    %865 = arith.constant 1 : i32
    %866 = llvm.mlir.constant(1 : i64) : i64
    %867 = llvm.alloca %866 x i32 : (i64) -> !llvm.ptr
    llvm.store %865, %867 : i32, !llvm.ptr
    %868 = arith.constant 2 : i32
    %869 = llvm.mlir.constant(1 : i64) : i64
    %870 = llvm.alloca %869 x i32 : (i64) -> !llvm.ptr
    llvm.store %868, %870 : i32, !llvm.ptr
    cf.br ^bb159
    ^bb159:
    %871 = llvm.load %870 : !llvm.ptr -> i32
    %872 = arith.constant 400 : i32
    %873 = arith.cmpi slt, %871, %872 : i32
    cf.cond_br %873, ^bb160, ^bb161
    ^bb160:
      %874 = llvm.load %864 : !llvm.ptr -> i128
      %876 = arith.trunci %856 : i128 to i64
      %877 = arith.trunci %874 : i128 to i64
      %875 = arith.muli %876, %877 : i64
      %878 = llvm.load %860 : !llvm.ptr -> i128
      %880 = arith.trunci %878 : i128 to i64
      %879 = arith.subi %875, %880 : i64
      %881 = arith.extsi %879 : i64 to i128
      %882 = llvm.load %864 : !llvm.ptr -> i128
      llvm.store %882, %860 : i128, !llvm.ptr
      llvm.store %881, %864 : i128, !llvm.ptr
      %883 = llvm.load %864 : !llvm.ptr -> i128
      %885 = arith.trunci %883 : i128 to i64
      %886 = arith.trunci %854 : i128 to i64
      %884 = arith.cmpi sgt, %885, %886 : i64
      cf.cond_br %884, ^bb162, ^bb163
      ^bb162:
        cf.br ^bb161
      ^bb163:
        cf.br ^bb164
      ^bb164:
      %887 = llvm.load %870 : !llvm.ptr -> i32
      llvm.store %887, %867 : i32, !llvm.ptr
      %888 = llvm.load %870 : !llvm.ptr -> i32
      %889 = arith.constant 1 : i32
      %890 = arith.addi %888, %889 : i32
      llvm.store %890, %870 : i32, !llvm.ptr
      cf.br ^bb159
    ^bb161:
    %891 = llvm.load %867 : !llvm.ptr -> i32
    func.return %891 : i32
  }
  func.func @main() -> i32 {
    %892 = func.call @maxJ_for_N() : () -> i32
    %893 = arith.constant 0 : i32
    %894 = arith.extsi %893 : i32 to i64
    %895 = llvm.mlir.constant(1 : i64) : i64
    %896 = llvm.alloca %895 x i64 : (i64) -> !llvm.ptr
    llvm.store %894, %896 : i64, !llvm.ptr
    %897 = arith.constant 1 : i32
    %898 = llvm.mlir.constant(1 : i64) : i64
    %899 = llvm.alloca %898 x i32 : (i64) -> !llvm.ptr
    llvm.store %897, %899 : i32, !llvm.ptr
    cf.br ^bb165
    ^bb165:
    %900 = llvm.load %899 : !llvm.ptr -> i32
    %901 = arith.cmpi slt, %900, %892 : i32
    cf.cond_br %901, ^bb166, ^bb167
    ^bb166:
      %902 = llvm.load %899 : !llvm.ptr -> i32
      %903 = arith.constant 1 : i32
      %904 = arith.addi %902, %903 : i32
      %905 = llvm.mlir.constant(1 : i64) : i64
      %906 = llvm.alloca %905 x i32 : (i64) -> !llvm.ptr
      llvm.store %904, %906 : i32, !llvm.ptr
      cf.br ^bb168
      ^bb168:
      %907 = llvm.load %906 : !llvm.ptr -> i32
      %908 = arith.cmpi sle, %907, %892 : i32
      cf.cond_br %908, ^bb169, ^bb170
      ^bb169:
        %910 = llvm.load %899 : !llvm.ptr -> i32
        %911 = arith.extsi %910 : i32 to i64
        %912 = llvm.load %906 : !llvm.ptr -> i32
        %913 = arith.extsi %912 : i32 to i64
        %909 = func.call @gcd_ll(%911, %913) : (i64, i64) -> i64
        %914 = arith.constant 1 : i32
        %916 = arith.extsi %914 : i32 to i64
        %915 = arith.cmpi eq, %909, %916 : i64
        cf.cond_br %915, ^bb171, ^bb172
        ^bb171:
          %918 = llvm.load %899 : !llvm.ptr -> i32
          %919 = llvm.load %906 : !llvm.ptr -> i32
          %917 = func.call @max_n_for_pair(%918, %919) : (i32, i32) -> i64
          %920 = arith.constant 0 : i32
          %922 = arith.extsi %920 : i32 to i64
          %921 = arith.cmpi sgt, %917, %922 : i64
          cf.cond_br %921, ^bb174, ^bb175
          ^bb174:
            %924 = llvm.load %899 : !llvm.ptr -> i32
            %925 = llvm.load %906 : !llvm.ptr -> i32
            %923 = func.call @sum_for_pair(%924, %925, %917) : (i32, i32, i64) -> i64
            %926 = llvm.load %896 : !llvm.ptr -> i64
            %927 = arith.addi %926, %923 : i64
            %928 = llvm.mlir.addressof @MOD : !llvm.ptr
            %929 = llvm.load %928 : !llvm.ptr -> i64
            %930 = arith.remsi %927, %929 : i64
            llvm.store %930, %896 : i64, !llvm.ptr
            cf.br ^bb176
          ^bb175:
            cf.br ^bb176
          ^bb176:
          cf.br ^bb173
        ^bb172:
          cf.br ^bb173
        ^bb173:
        %931 = llvm.load %906 : !llvm.ptr -> i32
        %932 = arith.constant 1 : i32
        %933 = arith.addi %931, %932 : i32
        llvm.store %933, %906 : i32, !llvm.ptr
        cf.br ^bb168
      ^bb170:
      %934 = llvm.load %899 : !llvm.ptr -> i32
      %935 = arith.constant 1 : i32
      %936 = arith.addi %934, %935 : i32
      llvm.store %936, %899 : i32, !llvm.ptr
      cf.br ^bb165
    ^bb167:
    %937 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %938 = llvm.load %896 : !llvm.ptr -> i64
    %939 = llvm.call @printf(%937, %938) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %940 = arith.constant 0 : i32
    func.return %940 : i32
  }
}