Problem 767

Window into a Matrix II: B(10^5, 10^16) mod 1e9+7. Uses 3-prime NTT convolution with CRT reconstruction.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 767
# Window into a Matrix II: B(10^5, 10^16) mod 1e9+7.
# Uses 3-prime NTT convolution with CRT reconstruction.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
    function malloc(n: i64) -> ptr<void>
    function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}

const MOD: i64 = 1000000007

const P1: i64 = 998244353
const P2: i64 = 1004535809
const P3: i64 = 469762049

let mut g_n: i64 = 0
let mut g_rev: ptr<i32> = null
let mut g_roots0: ptr<i64> = null
let mut g_roots1: ptr<i64> = null
let mut g_roots2: ptr<i64> = null
let mut g_roots_inv0: ptr<i64> = null
let mut g_roots_inv1: ptr<i64> = null
let mut g_roots_inv2: ptr<i64> = null
let mut g_inv_p1_mod_p2: i64 = 0
let mut g_p1_mod_p3: i64 = 0
let mut g_p12_mod_p3: i64 = 0
let mut g_inv_p12_mod_p3: i64 = 0
let mut g_p1_mod_mod: i64 = 0
let mut g_p12_mod_mod: i64 = 0

function mod_pow(a0: i64, e0: i64, mod: i64) -> i64 {
    let mut r: i64 = 1 % mod
    let mut a: i64 = a0 % mod
    if a < 0 { a = a + mod }
    let mut e: i64 = e0
    while e > 0 {
        if (e & 1) != 0 {
            r = ((r as i128) * (a as i128) % (mod as i128)) as i64
        }
        a = ((a as i128) * (a as i128) % (mod as i128)) as i64
        e = e >> 1
    }
    return r
}

function ceil_pow2(x: i64) -> i64 {
    let mut n: i64 = 1
    while n < x { n = n << 1 }
    return n
}

function ntt(a: ptr<i64>, n: i64, mod: i64, roots: ptr<i64>, roots_inv: ptr<i64>, rev: ptr<i32>, invert: i32) -> void {
    let mut i: i64 = 0
    while i < n {
        let j: i64 = rev[i] as i64
        if i < j {
            let t: i64 = a[i]
            a[i] = a[j]
            a[j] = t
        }
        i = i + 1
    }

    let r: ptr<i64> = if invert != 0 { roots_inv } else { roots }
    let mut length: i64 = 2
    while length <= n {
        let half: i64 = length >> 1
        let step: i64 = n / length
        let mut i0: i64 = 0
        while i0 < n {
            let mut idx: i64 = 0
            let mut j2: i64 = i0
            while j2 < i0 + half {
                let u: i64 = a[j2]
                let v: i64 = ((a[j2 + half] as i128) * (r[idx] as i128) % (mod as i128)) as i64
                let x: i64 = u + v
                if x >= mod { x = x - mod }
                let y: i64 = u - v
                if y < 0 { y = y + mod }
                a[j2] = x
                a[j2 + half] = y
                idx = idx + step
                j2 = j2 + 1
            }
            i0 = i0 + length
        }
        length = length << 1
    }

    if invert != 0 {
        let n_inv: i64 = mod_pow(n, mod - 2, mod)
        let mut i3: i64 = 0
        while i3 < n {
            a[i3] = ((a[i3] as i128) * (n_inv as i128) % (mod as i128)) as i64
            i3 = i3 + 1
        }
    }
}

function ctx_init(n: i64) -> void {
    g_n = n
    g_rev = malloc(n * 4) as ptr<i32>

    let mut j: i32 = 0
    let mut i: i64 = 1
    while i < n {
        let mut bit: i32 = (n >> 1) as i32
        while (j & bit) != 0 {
            j = j ^ bit
            bit = bit >> 1
        }
        j = j ^ bit
        g_rev[i] = j
        i = i + 1
    }
    g_rev[0] = 0

    let primes: array<i64, 3> = [P1, P2, P3]
    let gs: array<i64, 3> = [3, 3, 3]

    g_roots0 = malloc(n * 8) as ptr<i64>
    g_roots_inv0 = malloc(n * 8) as ptr<i64>
    g_roots1 = malloc(n * 8) as ptr<i64>
    g_roots_inv1 = malloc(n * 8) as ptr<i64>
    g_roots2 = malloc(n * 8) as ptr<i64>
    g_roots_inv2 = malloc(n * 8) as ptr<i64>

    let roots_arr: array<ptr<i64>, 3> = [g_roots0, g_roots1, g_roots2]
    let roots_inv_arr: array<ptr<i64>, 3> = [g_roots_inv0, g_roots_inv1, g_roots_inv2]

    let mut t: i32 = 0
    while t < 3 {
        let p: i64 = primes[t]
        let g: i64 = gs[t]
        let w: i64 = mod_pow(g, (p - 1) / n, p)
        let w_inv: i64 = mod_pow(w, p - 2, p)
        let roots: ptr<i64> = roots_arr[t]
        let roots_inv: ptr<i64> = roots_inv_arr[t]
        roots[0] = 1
        roots_inv[0] = 1
        let mut i2: i64 = 1
        while i2 < n {
            roots[i2] = ((roots[i2 - 1] as i128) * (w as i128) % (p as i128)) as i64
            roots_inv[i2] = ((roots_inv[i2 - 1] as i128) * (w_inv as i128) % (p as i128)) as i64
            i2 = i2 + 1
        }
        t = t + 1
    }

    g_inv_p1_mod_p2 = mod_pow(P1, P2 - 2, P2)
    g_p1_mod_p3 = P1 % P3
    g_p12_mod_p3 = ((P1 as i128) * (P2 as i128) % (P3 as i128)) as i64
    g_inv_p12_mod_p3 = mod_pow(g_p12_mod_p3, P3 - 2, P3)
    g_p1_mod_mod = P1 % MOD
    g_p12_mod_mod = ((P1 as i128) * (P2 as i128) % (MOD as i128)) as i64
}

function ctx_free() -> void {
    free(g_rev)
    free(g_roots0)
    free(g_roots_inv0)
    free(g_roots1)
    free(g_roots_inv1)
    free(g_roots2)
    free(g_roots_inv2)
}

function crt_reduce(out: ptr<i64>, c0: ptr<i64>, c1: ptr<i64>, c2: ptr<i64>, need: i64) -> void {
    let mut i: i64 = 0
    while i < need {
        let r1: i64 = c0[i]
        let r2: i64 = c1[i]
        let r3: i64 = c2[i]
        let t1: i64 = (((r2 - r1) % P2 + P2) % P2)
        let t1m: i64 = ((t1 as i128) * (g_inv_p1_mod_p2 as i128) % (P2 as i128)) as i64
        let x2_mod_p3: i64 = (r1 + ((g_p1_mod_p3 as i128) * (t1m as i128) % (P3 as i128)) as i64) % P3
        let t2: i64 = (((r3 - x2_mod_p3) % P3 + P3) % P3)
        let t2m: i64 = ((t2 as i128) * (g_inv_p12_mod_p3 as i128) % (P3 as i128)) as i64
        let v: i64 = (r1 + ((g_p1_mod_mod as i128) * (t1m % MOD as i128) % (MOD as i128)) as i64
                    + ((g_p12_mod_mod as i128) * (t2m % MOD as i128) % (MOD as i128)) as i64) % MOD
        out[i] = v
        i = i + 1
    }
}

function convolution_mod(a: ptr<i64>, la: i64, b: ptr<i64>, lb: i64) -> ptr<i64> {
    let need: i64 = la + lb - 1
    let n: i64 = g_n

    let primes: array<i64, 3> = [P1, P2, P3]
    let roots_arr: array<ptr<i64>, 3> = [g_roots0, g_roots1, g_roots2]
    let roots_inv_arr: array<ptr<i64>, 3> = [g_roots_inv0, g_roots_inv1, g_roots_inv2]

    let c0: ptr<i64> = malloc(need * 8) as ptr<i64>
    let c1: ptr<i64> = malloc(need * 8) as ptr<i64>
    let c2: ptr<i64> = malloc(need * 8) as ptr<i64>
    let convs: array<ptr<i64>, 3> = [c0, c1, c2]

    let mut t: i32 = 0
    while t < 3 {
        let p: i64 = primes[t]
        let fa: ptr<i64> = calloc(n, 8) as ptr<i64>
        let fb: ptr<i64> = calloc(n, 8) as ptr<i64>
        let mut i: i64 = 0
        while i < la {
            fa[i] = ((a[i] % p) + p) % p
            i = i + 1
        }
        i = 0
        while i < lb {
            fb[i] = ((b[i] % p) + p) % p
            i = i + 1
        }
        ntt(fa, n, p, roots_arr[t], roots_inv_arr[t], g_rev, 0)
        ntt(fb, n, p, roots_arr[t], roots_inv_arr[t], g_rev, 0)
        i = 0
        while i < n {
            fa[i] = ((fa[i] as i128) * (fb[i] as i128) % (p as i128)) as i64
            i = i + 1
        }
        ntt(fa, n, p, roots_arr[t], roots_inv_arr[t], g_rev, 1)
        memcpy(convs[t], fa, need * 8)
        free(fa)
        free(fb)
        t = t + 1
    }

    let out: ptr<i64> = malloc(need * 8) as ptr<i64>
    crt_reduce(out, c0, c1, c2, need)
    free(c0)
    free(c1)
    free(c2)
    return out
}

function convolution_square_mod(a: ptr<i64>, la: i64) -> ptr<i64> {
    let need: i64 = 2 * la - 1
    let n: i64 = g_n

    let primes: array<i64, 3> = [P1, P2, P3]
    let roots_arr: array<ptr<i64>, 3> = [g_roots0, g_roots1, g_roots2]
    let roots_inv_arr: array<ptr<i64>, 3> = [g_roots_inv0, g_roots_inv1, g_roots_inv2]

    let c0: ptr<i64> = malloc(need * 8) as ptr<i64>
    let c1: ptr<i64> = malloc(need * 8) as ptr<i64>
    let c2: ptr<i64> = malloc(need * 8) as ptr<i64>
    let convs: array<ptr<i64>, 3> = [c0, c1, c2]

    let mut t: i32 = 0
    while t < 3 {
        let p: i64 = primes[t]
        let fa: ptr<i64> = calloc(n, 8) as ptr<i64>
        let mut i: i64 = 0
        while i < la {
            fa[i] = ((a[i] % p) + p) % p
            i = i + 1
        }
        ntt(fa, n, p, roots_arr[t], roots_inv_arr[t], g_rev, 0)
        i = 0
        while i < n {
            fa[i] = ((fa[i] as i128) * (fa[i] as i128) % (p as i128)) as i64
            i = i + 1
        }
        ntt(fa, n, p, roots_arr[t], roots_inv_arr[t], g_rev, 1)
        memcpy(convs[t], fa, need * 8)
        free(fa)
        t = t + 1
    }

    let out: ptr<i64> = malloc(need * 8) as ptr<i64>
    crt_reduce(out, c0, c1, c2, need)
    free(c0)
    free(c1)
    free(c2)
    return out
}

function pow16_mod(x: i64) -> i64 {
    let x2: i64 = ((x as i128) * (x as i128) % (MOD as i128)) as i64
    let x4: i64 = ((x2 as i128) * (x2 as i128) % (MOD as i128)) as i64
    let x8: i64 = ((x4 as i128) * (x4 as i128) % (MOD as i128)) as i64
    return ((x8 as i128) * (x8 as i128) % (MOD as i128)) as i64
}

function main() -> i32 {
    let k: i64 = 100000
    let n: i64 = 10000000000000000
    let m: i64 = n / k
    let A: i64 = mod_pow(2, m % (MOD - 1), MOD)

    let fact: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    let inv_fact: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    fact[0] = 1
    let mut i: i64 = 1
    while i <= k {
        fact[i] = ((fact[i - 1] as i128) * (i as i128) % (MOD as i128)) as i64
        i = i + 1
    }
    inv_fact[k] = mod_pow(fact[k], MOD - 2, MOD)
    i = k
    while i >= 1 {
        inv_fact[i - 1] = ((inv_fact[i] as i128) * (i as i128) % (MOD as i128)) as i64
        i = i - 1
    }

    let fact16: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    let inv_fact16: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    i = 0
    while i <= k {
        fact16[i] = pow16_mod(fact[i])
        inv_fact16[i] = pow16_mod(inv_fact[i])
        i = i + 1
    }

    let need: i64 = 2 * (k + 1) - 1
    let ntt_len: i64 = ceil_pow2(need)
    ctx_init(ntt_len)

    let conv_aa: ptr<i64> = convolution_square_mod(inv_fact16, k + 1)

    let f: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    i = 0
    while i <= k {
        f[i] = ((fact16[i] as i128) * (conv_aa[i] as i128) % (MOD as i128)) as i64
        i = i + 1
    }
    free(conv_aa)

    let fprime: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    i = 0
    while i <= k {
        fprime[i] = ((f[i] as i128) * (inv_fact[i] as i128) % (MOD as i128)) as i64
        i = i + 1
    }

    let neg2: i64 = MOD - 2
    let b: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    let mut p: i64 = 1
    i = 0
    while i <= k {
        b[i] = ((p as i128) * (inv_fact[i] as i128) % (MOD as i128)) as i64
        p = ((p as i128) * (neg2 as i128) % (MOD as i128)) as i64
        i = i + 1
    }

    let conv_fb: ptr<i64> = convolution_mod(fprime, k + 1, b, k + 1)

    let S: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    i = 0
    while i <= k {
        S[i] = ((conv_fb[i] as i128) * (fact[i] as i128) % (MOD as i128)) as i64
        i = i + 1
    }
    free(conv_fb)

    let powA: ptr<i64> = malloc((k + 1) * 8) as ptr<i64>
    powA[0] = 1
    i = 1
    while i <= k {
        powA[i] = ((powA[i - 1] as i128) * (A as i128) % (MOD as i128)) as i64
        i = i + 1
    }

    let fk: i64 = fact[k]
    let mut ans: i64 = 0
    i = 0
    while i <= k {
        let comb: i64 = ((fk as i128) * (inv_fact[i] as i128) % (MOD as i128)) as i64
        let comb2: i64 = ((comb as i128) * (inv_fact[k - i] as i128) % (MOD as i128)) as i64
        let term: i64 = ((comb2 as i128) * (powA[i] as i128) % (MOD as i128)) as i64
        let term2: i64 = ((term as i128) * (S[k - i] as i128) % (MOD as i128)) as i64
        ans = (ans + term2) % MOD
        i = i + 1
    }

    free(fact)
    free(inv_fact)
    free(fact16)
    free(inv_fact16)
    free(f)
    free(fprime)
    free(b)
    free(S)
    free(powA)
    ctx_free()

    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 mod_pow_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod);
int64_t ceil_pow2_i64(int64_t x);
void ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(int64_t* a, int64_t n, int64_t mod, int64_t* roots, int64_t* roots_inv, int32_t* rev, int32_t invert);
void ctx_init_i64(int64_t n);
void ctx_free(void);
void crt_reduce_ptr_i64_ptr_i64_ptr_i64_ptr_i64_i64(int64_t* out, int64_t* c0, int64_t* c1, int64_t* c2, int64_t need);
int64_t* convolution_mod_ptr_i64_i64_ptr_i64_i64(int64_t* a, int64_t la, int64_t* b, int64_t lb);
int64_t* convolution_square_mod_ptr_i64_i64(int64_t* a, int64_t la);
int64_t pow16_mod_i64(int64_t x);
int32_t main(void);

static const int64_t MOD = 1000000007;
static const int64_t P1 = 998244353;
static const int64_t P2 = 1004535809;
static const int64_t P3 = 469762049;

/* Module statics */
static int64_t g_n = 0;
static int32_t* g_rev = NULL;
static int64_t* g_roots0 = NULL;
static int64_t* g_roots1 = NULL;
static int64_t* g_roots2 = NULL;
static int64_t* g_roots_inv0 = NULL;
static int64_t* g_roots_inv1 = NULL;
static int64_t* g_roots_inv2 = NULL;
static int64_t g_inv_p1_mod_p2 = 0;
static int64_t g_p1_mod_p3 = 0;
static int64_t g_p12_mod_p3 = 0;
static int64_t g_inv_p12_mod_p3 = 0;
static int64_t g_p1_mod_mod = 0;
static int64_t g_p12_mod_mod = 0;





int64_t mod_pow_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod) {
    int64_t r = FLOW_CHECKED_MOD((1), (mod));
    int64_t a = FLOW_CHECKED_MOD((a0), (mod));
    if (a < 0) {
        a = (a + mod);
    }
    int64_t e = e0;
    while (e > 0) {
        if ((e & 1) != 0) {
            r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(a)))), (((__int128)(mod))))));
        }
        a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(a)))), (((__int128)(mod))))));
        e = FLOW_CHECKED_SHR((e), (1));
    }
    return r;
}

int64_t ceil_pow2_i64(int64_t x) {
    int64_t n = 1;
    while (n < x) {
        n = FLOW_CHECKED_SHL((n), (1));
    }
    return n;
}

void ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(int64_t* a, int64_t n, int64_t mod, int64_t* roots, int64_t* roots_inv, int32_t* rev, int32_t invert) {
    int64_t i = 0;
    while (i < n) {
        int64_t j = ((int64_t)(rev[i]));
        if (i < j) {
            int64_t t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        i = (i + 1);
    }
    int64_t* r = (int64_t*)(((invert != 0) ? (roots_inv) : (roots)));
    int64_t length = 2;
    while (length <= n) {
        int64_t half = FLOW_CHECKED_SHR((length), (1));
        int64_t step = FLOW_CHECKED_DIV((n), (length));
        int64_t i0 = 0;
        while (i0 < n) {
            int64_t idx = 0;
            int64_t j2 = i0;
            while (j2 < (i0 + half)) {
                int64_t u = a[j2];
                int64_t v = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a[(j2 + half)])) * ((__int128)(r[idx])))), (((__int128)(mod))))));
                int64_t x = (u + v);
                if (x >= mod) {
                    x = (x - mod);
                }
                int64_t y = (u - v);
                if (y < 0) {
                    y = (y + mod);
                }
                a[j2] = x;
                a[(j2 + half)] = y;
                idx = (idx + step);
                j2 = (j2 + 1);
            }
            i0 = (i0 + length);
        }
        length = FLOW_CHECKED_SHL((length), (1));
    }
    if (invert != 0) {
        int64_t n_inv = mod_pow_i64_i64_i64(n, (mod - 2), mod);
        int64_t i3 = 0;
        while (i3 < n) {
            a[i3] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a[i3])) * ((__int128)(n_inv)))), (((__int128)(mod))))));
            i3 = (i3 + 1);
        }
    }
}

void ctx_init_i64(int64_t n) {
    g_n = n;
    g_rev = ((int32_t*)(malloc((n * 4))));
    int32_t j = 0;
    int64_t i = 1;
    while (i < n) {
        int32_t bit = ((int32_t)(FLOW_CHECKED_SHR((n), (1))));
        while ((j & bit) != 0) {
            j = (j ^ bit);
            bit = FLOW_CHECKED_SHR((bit), (1));
        }
        j = (j ^ bit);
        g_rev[i] = j;
        i = (i + 1);
    }
    g_rev[0] = 0;
    int64_t primes[3] = { P1, P2, P3 };
    int64_t gs[3] = { 3, 3, 3 };
    g_roots0 = ((int64_t*)(malloc((n * 8))));
    g_roots_inv0 = ((int64_t*)(malloc((n * 8))));
    g_roots1 = ((int64_t*)(malloc((n * 8))));
    g_roots_inv1 = ((int64_t*)(malloc((n * 8))));
    g_roots2 = ((int64_t*)(malloc((n * 8))));
    g_roots_inv2 = ((int64_t*)(malloc((n * 8))));
    int64_t* roots_arr[3] = { g_roots0, g_roots1, g_roots2 };
    int64_t* roots_inv_arr[3] = { g_roots_inv0, g_roots_inv1, g_roots_inv2 };
    int32_t t = 0;
    while (t < 3) {
        int64_t p = (((unsigned)(t) < 3) ? primes[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), primes[0]));
        int64_t g = (((unsigned)(t) < 3) ? gs[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), gs[0]));
        int64_t w = mod_pow_i64_i64_i64(g, FLOW_CHECKED_DIV(((p - 1)), (n)), p);
        int64_t w_inv = mod_pow_i64_i64_i64(w, (p - 2), p);
        int64_t* roots = (int64_t*)((((unsigned)(t) < 3) ? roots_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_arr[0])));
        int64_t* roots_inv = (int64_t*)((((unsigned)(t) < 3) ? roots_inv_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_inv_arr[0])));
        roots[0] = 1;
        roots_inv[0] = 1;
        int64_t i2 = 1;
        while (i2 < n) {
            roots[i2] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(roots[(i2 - 1)])) * ((__int128)(w)))), (((__int128)(p))))));
            roots_inv[i2] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(roots_inv[(i2 - 1)])) * ((__int128)(w_inv)))), (((__int128)(p))))));
            i2 = (i2 + 1);
        }
        t = (t + 1);
    }
    g_inv_p1_mod_p2 = mod_pow_i64_i64_i64(P1, (P2 - 2), P2);
    g_p1_mod_p3 = FLOW_CHECKED_MOD((P1), (P3));
    g_p12_mod_p3 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(P1)) * ((__int128)(P2)))), (((__int128)(P3))))));
    g_inv_p12_mod_p3 = mod_pow_i64_i64_i64(g_p12_mod_p3, (P3 - 2), P3);
    g_p1_mod_mod = FLOW_CHECKED_MOD((P1), (MOD));
    g_p12_mod_mod = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(P1)) * ((__int128)(P2)))), (((__int128)(MOD))))));
}

void ctx_free(void) {
    free(g_rev);
    free(g_roots0);
    free(g_roots_inv0);
    free(g_roots1);
    free(g_roots_inv1);
    free(g_roots2);
    free(g_roots_inv2);
}

void crt_reduce_ptr_i64_ptr_i64_ptr_i64_ptr_i64_i64(int64_t* out, int64_t* c0, int64_t* c1, int64_t* c2, int64_t need) {
    int64_t i = 0;
    while (i < need) {
        int64_t r1 = c0[i];
        int64_t r2 = c1[i];
        int64_t r3 = c2[i];
        int64_t t1 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((r2 - r1)), (P2)) + P2)), (P2));
        int64_t t1m = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(t1)) * ((__int128)(g_inv_p1_mod_p2)))), (((__int128)(P2))))));
        int64_t x2_mod_p3 = FLOW_CHECKED_MOD(((r1 + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g_p1_mod_p3)) * ((__int128)(t1m)))), (((__int128)(P3)))))))), (P3));
        int64_t t2 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((r3 - x2_mod_p3)), (P3)) + P3)), (P3));
        int64_t t2m = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(t2)) * ((__int128)(g_inv_p12_mod_p3)))), (((__int128)(P3))))));
        int64_t v = FLOW_CHECKED_MOD((((r1 + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g_p1_mod_mod)) * FLOW_CHECKED_MOD((t1m), (((__int128)(MOD)))))), (((__int128)(MOD))))))) + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g_p12_mod_mod)) * FLOW_CHECKED_MOD((t2m), (((__int128)(MOD)))))), (((__int128)(MOD)))))))), (MOD));
        out[i] = v;
        i = (i + 1);
    }
}

int64_t* convolution_mod_ptr_i64_i64_ptr_i64_i64(int64_t* a, int64_t la, int64_t* b, int64_t lb) {
    int64_t need = ((la + lb) - 1);
    int64_t n = g_n;
    int64_t primes[3] = { P1, P2, P3 };
    int64_t* roots_arr[3] = { g_roots0, g_roots1, g_roots2 };
    int64_t* roots_inv_arr[3] = { g_roots_inv0, g_roots_inv1, g_roots_inv2 };
    int64_t* c0 = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    int64_t* c1 = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    int64_t* c2 = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    int64_t* convs[3] = { c0, c1, c2 };
    int32_t t = 0;
    while (t < 3) {
        int64_t p = (((unsigned)(t) < 3) ? primes[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), primes[0]));
        int64_t* fa = (int64_t*)(((int64_t*)(calloc(n, 8))));
        int64_t* fb = (int64_t*)(((int64_t*)(calloc(n, 8))));
        int64_t i = 0;
        while (i < la) {
            fa[i] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a[i]), (p)) + p)), (p));
            i = (i + 1);
        }
        i = 0;
        while (i < lb) {
            fb[i] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((b[i]), (p)) + p)), (p));
            i = (i + 1);
        }
        ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(fa, n, p, (((unsigned)(t) < 3) ? roots_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_arr[0])), (((unsigned)(t) < 3) ? roots_inv_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_inv_arr[0])), g_rev, 0);
        ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(fb, n, p, (((unsigned)(t) < 3) ? roots_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_arr[0])), (((unsigned)(t) < 3) ? roots_inv_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_inv_arr[0])), g_rev, 0);
        i = 0;
        while (i < n) {
            fa[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fa[i])) * ((__int128)(fb[i])))), (((__int128)(p))))));
            i = (i + 1);
        }
        ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(fa, n, p, (((unsigned)(t) < 3) ? roots_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_arr[0])), (((unsigned)(t) < 3) ? roots_inv_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_inv_arr[0])), g_rev, 1);
        memcpy((((unsigned)(t) < 3) ? convs[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), convs[0])), fa, (need * 8));
        free(fa);
        free(fb);
        t = (t + 1);
    }
    int64_t* out = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    crt_reduce_ptr_i64_ptr_i64_ptr_i64_ptr_i64_i64(out, c0, c1, c2, need);
    free(c0);
    free(c1);
    free(c2);
    return out;
}

int64_t* convolution_square_mod_ptr_i64_i64(int64_t* a, int64_t la) {
    int64_t need = ((2 * la) - 1);
    int64_t n = g_n;
    int64_t primes[3] = { P1, P2, P3 };
    int64_t* roots_arr[3] = { g_roots0, g_roots1, g_roots2 };
    int64_t* roots_inv_arr[3] = { g_roots_inv0, g_roots_inv1, g_roots_inv2 };
    int64_t* c0 = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    int64_t* c1 = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    int64_t* c2 = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    int64_t* convs[3] = { c0, c1, c2 };
    int32_t t = 0;
    while (t < 3) {
        int64_t p = (((unsigned)(t) < 3) ? primes[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), primes[0]));
        int64_t* fa = (int64_t*)(((int64_t*)(calloc(n, 8))));
        int64_t i = 0;
        while (i < la) {
            fa[i] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a[i]), (p)) + p)), (p));
            i = (i + 1);
        }
        ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(fa, n, p, (((unsigned)(t) < 3) ? roots_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_arr[0])), (((unsigned)(t) < 3) ? roots_inv_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_inv_arr[0])), g_rev, 0);
        i = 0;
        while (i < n) {
            fa[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fa[i])) * ((__int128)(fa[i])))), (((__int128)(p))))));
            i = (i + 1);
        }
        ntt_ptr_i64_i64_i64_ptr_i64_ptr_i64_ptr_i32_i32(fa, n, p, (((unsigned)(t) < 3) ? roots_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_arr[0])), (((unsigned)(t) < 3) ? roots_inv_arr[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), roots_inv_arr[0])), g_rev, 1);
        memcpy((((unsigned)(t) < 3) ? convs[t] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(t), 3), flow_fault_handler("array index out of bounds"), convs[0])), fa, (need * 8));
        free(fa);
        t = (t + 1);
    }
    int64_t* out = (int64_t*)(((int64_t*)(malloc((need * 8)))));
    crt_reduce_ptr_i64_ptr_i64_ptr_i64_ptr_i64_i64(out, c0, c1, c2, need);
    free(c0);
    free(c1);
    free(c2);
    return out;
}

int64_t pow16_mod_i64(int64_t x) {
    int64_t x2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(x)) * ((__int128)(x)))), (((__int128)(MOD))))));
    int64_t x4 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(x2)) * ((__int128)(x2)))), (((__int128)(MOD))))));
    int64_t x8 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(x4)) * ((__int128)(x4)))), (((__int128)(MOD))))));
    return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(x8)) * ((__int128)(x8)))), (((__int128)(MOD))))));
}

int32_t main(void) {
    int64_t k = 100000;
    int64_t n = 10000000000000000;
    int64_t m = FLOW_CHECKED_DIV((n), (k));
    int64_t A = mod_pow_i64_i64_i64(2, FLOW_CHECKED_MOD((m), ((MOD - 1))), MOD);
    int64_t* fact = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    int64_t* inv_fact = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    fact[0] = 1;
    int64_t i = 1;
    while (i <= k) {
        fact[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fact[(i - 1)])) * ((__int128)(i)))), (((__int128)(MOD))))));
        i = (i + 1);
    }
    inv_fact[k] = mod_pow_i64_i64_i64(fact[k], (MOD - 2), MOD);
    i = k;
    while (i >= 1) {
        inv_fact[(i - 1)] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(inv_fact[i])) * ((__int128)(i)))), (((__int128)(MOD))))));
        i = (i - 1);
    }
    int64_t* fact16 = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    int64_t* inv_fact16 = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    i = 0;
    while (i <= k) {
        fact16[i] = pow16_mod_i64(fact[i]);
        inv_fact16[i] = pow16_mod_i64(inv_fact[i]);
        i = (i + 1);
    }
    int64_t need = ((2 * (k + 1)) - 1);
    int64_t ntt_len = ceil_pow2_i64(need);
    ctx_init_i64(ntt_len);
    int64_t* conv_aa = (int64_t*)(convolution_square_mod_ptr_i64_i64(inv_fact16, (k + 1)));
    int64_t* f = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    i = 0;
    while (i <= k) {
        f[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fact16[i])) * ((__int128)(conv_aa[i])))), (((__int128)(MOD))))));
        i = (i + 1);
    }
    free(conv_aa);
    int64_t* fprime = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    i = 0;
    while (i <= k) {
        fprime[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f[i])) * ((__int128)(inv_fact[i])))), (((__int128)(MOD))))));
        i = (i + 1);
    }
    int64_t neg2 = (MOD - 2);
    int64_t* b = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    int64_t p = 1;
    i = 0;
    while (i <= k) {
        b[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(p)) * ((__int128)(inv_fact[i])))), (((__int128)(MOD))))));
        p = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(p)) * ((__int128)(neg2)))), (((__int128)(MOD))))));
        i = (i + 1);
    }
    int64_t* conv_fb = (int64_t*)(convolution_mod_ptr_i64_i64_ptr_i64_i64(fprime, (k + 1), b, (k + 1)));
    int64_t* S = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    i = 0;
    while (i <= k) {
        S[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(conv_fb[i])) * ((__int128)(fact[i])))), (((__int128)(MOD))))));
        i = (i + 1);
    }
    free(conv_fb);
    int64_t* powA = (int64_t*)(((int64_t*)(malloc(((k + 1) * 8)))));
    powA[0] = 1;
    i = 1;
    while (i <= k) {
        powA[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(powA[(i - 1)])) * ((__int128)(A)))), (((__int128)(MOD))))));
        i = (i + 1);
    }
    int64_t fk = fact[k];
    int64_t ans = 0;
    i = 0;
    while (i <= k) {
        int64_t comb = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fk)) * ((__int128)(inv_fact[i])))), (((__int128)(MOD))))));
        int64_t comb2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(comb)) * ((__int128)(inv_fact[(k - i)])))), (((__int128)(MOD))))));
        int64_t term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(comb2)) * ((__int128)(powA[i])))), (((__int128)(MOD))))));
        int64_t term2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(term)) * ((__int128)(S[(k - i)])))), (((__int128)(MOD))))));
        ans = FLOW_CHECKED_MOD(((ans + term2)), (MOD));
        i = (i + 1);
    }
    free(fact);
    free(inv_fact);
    free(fact16);
    free(inv_fact16);
    free(f);
    free(fprime);
    free(b);
    free(S);
    free(powA);
    ctx_free();
    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 private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  func.func private @malloc(i64) -> !llvm.ptr
  func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
  // Constant: MOD
  llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
  // Constant: P1
  llvm.mlir.global internal constant @P1(998244353 : i64) : i64
  // Constant: P2
  llvm.mlir.global internal constant @P2(1004535809 : i64) : i64
  // Constant: P3
  llvm.mlir.global internal constant @P3(469762049 : i64) : i64
  // Module static: g_n
  llvm.mlir.global internal @g_n(0 : i64) : i64
  // Module static: g_rev
  llvm.mlir.global internal @g_rev() {addr_space = 0 : i32} : !llvm.ptr {
    %0 = llvm.mlir.zero : !llvm.ptr
    llvm.return %0 : !llvm.ptr
  }
  // Module static: g_roots0
  llvm.mlir.global internal @g_roots0() {addr_space = 0 : i32} : !llvm.ptr {
    %1 = llvm.mlir.zero : !llvm.ptr
    llvm.return %1 : !llvm.ptr
  }
  // Module static: g_roots1
  llvm.mlir.global internal @g_roots1() {addr_space = 0 : i32} : !llvm.ptr {
    %2 = llvm.mlir.zero : !llvm.ptr
    llvm.return %2 : !llvm.ptr
  }
  // Module static: g_roots2
  llvm.mlir.global internal @g_roots2() {addr_space = 0 : i32} : !llvm.ptr {
    %3 = llvm.mlir.zero : !llvm.ptr
    llvm.return %3 : !llvm.ptr
  }
  // Module static: g_roots_inv0
  llvm.mlir.global internal @g_roots_inv0() {addr_space = 0 : i32} : !llvm.ptr {
    %4 = llvm.mlir.zero : !llvm.ptr
    llvm.return %4 : !llvm.ptr
  }
  // Module static: g_roots_inv1
  llvm.mlir.global internal @g_roots_inv1() {addr_space = 0 : i32} : !llvm.ptr {
    %5 = llvm.mlir.zero : !llvm.ptr
    llvm.return %5 : !llvm.ptr
  }
  // Module static: g_roots_inv2
  llvm.mlir.global internal @g_roots_inv2() {addr_space = 0 : i32} : !llvm.ptr {
    %6 = llvm.mlir.zero : !llvm.ptr
    llvm.return %6 : !llvm.ptr
  }
  // Module static: g_inv_p1_mod_p2
  llvm.mlir.global internal @g_inv_p1_mod_p2(0 : i64) : i64
  // Module static: g_p1_mod_p3
  llvm.mlir.global internal @g_p1_mod_p3(0 : i64) : i64
  // Module static: g_p12_mod_p3
  llvm.mlir.global internal @g_p12_mod_p3(0 : i64) : i64
  // Module static: g_inv_p12_mod_p3
  llvm.mlir.global internal @g_inv_p12_mod_p3(0 : i64) : i64
  // Module static: g_p1_mod_mod
  llvm.mlir.global internal @g_p1_mod_mod(0 : i64) : i64
  // Module static: g_p12_mod_mod
  llvm.mlir.global internal @g_p12_mod_mod(0 : i64) : i64
  func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %7 = arith.constant 1 : i32
    %9 = arith.extsi %7 : i32 to i64
    %8 = arith.remsi %9, %arg2 : i64
    %10 = llvm.mlir.constant(1 : i64) : i64
    %11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
    llvm.store %8, %11 : i64, !llvm.ptr
    %12 = arith.remsi %arg0, %arg2 : i64
    %13 = llvm.mlir.constant(1 : i64) : i64
    %14 = llvm.alloca %13 x i64 : (i64) -> !llvm.ptr
    llvm.store %12, %14 : i64, !llvm.ptr
    %15 = llvm.load %14 : !llvm.ptr -> i64
    %16 = arith.constant 0 : i32
    %18 = arith.extsi %16 : i32 to i64
    %17 = arith.cmpi slt, %15, %18 : i64
    cf.cond_br %17, ^bb0, ^bb1
    ^bb0:
      %19 = llvm.load %14 : !llvm.ptr -> i64
      %20 = arith.addi %19, %arg2 : i64
      llvm.store %20, %14 : i64, !llvm.ptr
      cf.br ^bb2
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %21 = llvm.mlir.constant(1 : i64) : i64
    %22 = llvm.alloca %21 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %22 : i64, !llvm.ptr
    cf.br ^bb3
    ^bb3:
    %23 = llvm.load %22 : !llvm.ptr -> i64
    %24 = arith.constant 0 : i32
    %26 = arith.extsi %24 : i32 to i64
    %25 = arith.cmpi sgt, %23, %26 : i64
    cf.cond_br %25, ^bb4, ^bb5
    ^bb4:
      %27 = llvm.load %22 : !llvm.ptr -> i64
      %28 = arith.constant 1 : i32
      %30 = arith.extsi %28 : i32 to i64
      %29 = arith.andi %27, %30 : i64
      %31 = arith.constant 0 : i32
      %33 = arith.extsi %31 : i32 to i64
      %32 = arith.cmpi ne, %29, %33 : i64
      cf.cond_br %32, ^bb6, ^bb7
      ^bb6:
        %34 = llvm.load %11 : !llvm.ptr -> i64
        %35 = arith.extsi %34 : i64 to i128
        %36 = llvm.load %14 : !llvm.ptr -> i64
        %37 = arith.extsi %36 : i64 to i128
        %39 = arith.trunci %35 : i128 to i64
        %40 = arith.trunci %37 : i128 to i64
        %38 = arith.muli %39, %40 : i64
        %41 = arith.extsi %arg2 : i64 to i128
        %43 = arith.trunci %41 : i128 to i64
        %42 = arith.remsi %38, %43 : i64
        llvm.store %42, %11 : i64, !llvm.ptr
        cf.br ^bb8
      ^bb7:
        cf.br ^bb8
      ^bb8:
      %44 = llvm.load %14 : !llvm.ptr -> i64
      %45 = arith.extsi %44 : i64 to i128
      %46 = llvm.load %14 : !llvm.ptr -> i64
      %47 = arith.extsi %46 : i64 to i128
      %49 = arith.trunci %45 : i128 to i64
      %50 = arith.trunci %47 : i128 to i64
      %48 = arith.muli %49, %50 : i64
      %51 = arith.extsi %arg2 : i64 to i128
      %53 = arith.trunci %51 : i128 to i64
      %52 = arith.remsi %48, %53 : i64
      llvm.store %52, %14 : i64, !llvm.ptr
      %54 = llvm.load %22 : !llvm.ptr -> i64
      %55 = arith.constant 1 : i32
      %57 = arith.extsi %55 : i32 to i64
      %56 = arith.shrsi %54, %57 : i64
      llvm.store %56, %22 : i64, !llvm.ptr
      cf.br ^bb3
    ^bb5:
    %58 = llvm.load %11 : !llvm.ptr -> i64
    func.return %58 : i64
  }
  func.func @ceil_pow2(%arg0: i64) -> i64 {
    %59 = arith.constant 1 : i32
    %60 = arith.extsi %59 : i32 to i64
    %61 = llvm.mlir.constant(1 : i64) : i64
    %62 = llvm.alloca %61 x i64 : (i64) -> !llvm.ptr
    llvm.store %60, %62 : i64, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %63 = llvm.load %62 : !llvm.ptr -> i64
    %64 = arith.cmpi slt, %63, %arg0 : i64
    cf.cond_br %64, ^bb10, ^bb11
    ^bb10:
      %65 = llvm.load %62 : !llvm.ptr -> i64
      %66 = arith.constant 1 : i32
      %68 = arith.extsi %66 : i32 to i64
      %67 = arith.shli %65, %68 : i64
      llvm.store %67, %62 : i64, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %69 = llvm.load %62 : !llvm.ptr -> i64
    func.return %69 : i64
  }
  func.func @ntt(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: i32) -> () {
    %70 = arith.constant 0 : i32
    %71 = arith.extsi %70 : i32 to i64
    %72 = llvm.mlir.constant(1 : i64) : i64
    %73 = llvm.alloca %72 x i64 : (i64) -> !llvm.ptr
    llvm.store %71, %73 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %74 = llvm.load %73 : !llvm.ptr -> i64
    %75 = arith.cmpi slt, %74, %arg1 : i64
    cf.cond_br %75, ^bb13, ^bb14
    ^bb13:
      %77 = llvm.load %73 : !llvm.ptr -> i64
      %78 = llvm.getelementptr %arg5[%77] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %76 = llvm.load %78 : !llvm.ptr -> i32
      %79 = arith.extsi %76 : i32 to i64
      %80 = llvm.load %73 : !llvm.ptr -> i64
      %81 = arith.cmpi slt, %80, %79 : i64
      cf.cond_br %81, ^bb15, ^bb16
      ^bb15:
        %83 = llvm.load %73 : !llvm.ptr -> i64
        %84 = llvm.getelementptr %arg0[%83] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %82 = llvm.load %84 : !llvm.ptr -> i64
        %86 = llvm.getelementptr %arg0[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %85 = llvm.load %86 : !llvm.ptr -> i64
        %87 = llvm.load %73 : !llvm.ptr -> i64
        %88 = llvm.getelementptr %arg0[%87] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %85, %88 : i64, !llvm.ptr
        %89 = llvm.getelementptr %arg0[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %82, %89 : i64, !llvm.ptr
        cf.br ^bb17
      ^bb16:
        cf.br ^bb17
      ^bb17:
      %90 = llvm.load %73 : !llvm.ptr -> i64
      %91 = arith.constant 1 : i32
      %93 = arith.extsi %91 : i32 to i64
      %92 = arith.addi %90, %93 : i64
      llvm.store %92, %73 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %94 = arith.constant 0 : i32
    %95 = arith.cmpi ne, %arg6, %94 : i32
    %96 = scf.if %95 -> (!llvm.ptr) {
      scf.yield %arg4 : !llvm.ptr
    } else {
      scf.yield %arg3 : !llvm.ptr
    }
    %97 = arith.constant 2 : i32
    %98 = arith.extsi %97 : i32 to i64
    %99 = llvm.mlir.constant(1 : i64) : i64
    %100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
    llvm.store %98, %100 : i64, !llvm.ptr
    cf.br ^bb18
    ^bb18:
    %101 = llvm.load %100 : !llvm.ptr -> i64
    %102 = arith.cmpi sle, %101, %arg1 : i64
    cf.cond_br %102, ^bb19, ^bb20
    ^bb19:
      %103 = llvm.load %100 : !llvm.ptr -> i64
      %104 = arith.constant 1 : i32
      %106 = arith.extsi %104 : i32 to i64
      %105 = arith.shrsi %103, %106 : i64
      %107 = llvm.load %100 : !llvm.ptr -> i64
      %108 = arith.divsi %arg1, %107 : i64
      %109 = arith.constant 0 : i32
      %110 = arith.extsi %109 : i32 to i64
      %111 = llvm.mlir.constant(1 : i64) : i64
      %112 = llvm.alloca %111 x i64 : (i64) -> !llvm.ptr
      llvm.store %110, %112 : i64, !llvm.ptr
      cf.br ^bb21
      ^bb21:
      %113 = llvm.load %112 : !llvm.ptr -> i64
      %114 = arith.cmpi slt, %113, %arg1 : i64
      cf.cond_br %114, ^bb22, ^bb23
      ^bb22:
        %115 = arith.constant 0 : i32
        %116 = arith.extsi %115 : i32 to i64
        %117 = llvm.mlir.constant(1 : i64) : i64
        %118 = llvm.alloca %117 x i64 : (i64) -> !llvm.ptr
        llvm.store %116, %118 : i64, !llvm.ptr
        %119 = llvm.load %112 : !llvm.ptr -> i64
        %120 = llvm.mlir.constant(1 : i64) : i64
        %121 = llvm.alloca %120 x i64 : (i64) -> !llvm.ptr
        llvm.store %119, %121 : i64, !llvm.ptr
        cf.br ^bb24
        ^bb24:
        %122 = llvm.load %121 : !llvm.ptr -> i64
        %123 = llvm.load %112 : !llvm.ptr -> i64
        %124 = arith.addi %123, %105 : i64
        %125 = arith.cmpi slt, %122, %124 : i64
        cf.cond_br %125, ^bb25, ^bb26
        ^bb25:
          %127 = llvm.load %121 : !llvm.ptr -> i64
          %128 = llvm.getelementptr %arg0[%127] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %126 = llvm.load %128 : !llvm.ptr -> i64
          %130 = llvm.load %121 : !llvm.ptr -> i64
          %131 = arith.addi %130, %105 : i64
          %132 = llvm.getelementptr %arg0[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %129 = llvm.load %132 : !llvm.ptr -> i64
          %133 = arith.extsi %129 : i64 to i128
          %135 = llvm.load %118 : !llvm.ptr -> i64
          %136 = llvm.getelementptr %96[%135] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %134 = llvm.load %136 : !llvm.ptr -> i64
          %137 = arith.extsi %134 : i64 to i128
          %139 = arith.trunci %133 : i128 to i64
          %140 = arith.trunci %137 : i128 to i64
          %138 = arith.muli %139, %140 : i64
          %141 = arith.extsi %arg2 : i64 to i128
          %143 = arith.trunci %141 : i128 to i64
          %142 = arith.remsi %138, %143 : i64
          %144 = arith.addi %126, %142 : i64
          %145 = arith.cmpi sge, %144, %arg2 : i64
          %146 = scf.if %145 -> (i64) {
            %147 = arith.subi %144, %arg2 : i64
            scf.yield %147 : i64
          } else {
            scf.yield %144 : i64
          }
          %148 = arith.subi %126, %142 : i64
          %149 = arith.constant 0 : i32
          %151 = arith.extsi %149 : i32 to i64
          %150 = arith.cmpi slt, %148, %151 : i64
          %152 = scf.if %150 -> (i64) {
            %153 = arith.addi %148, %arg2 : i64
            scf.yield %153 : i64
          } else {
            scf.yield %148 : i64
          }
          %154 = llvm.load %121 : !llvm.ptr -> i64
          %155 = llvm.getelementptr %arg0[%154] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %146, %155 : i64, !llvm.ptr
          %156 = llvm.load %121 : !llvm.ptr -> i64
          %157 = arith.addi %156, %105 : i64
          %158 = llvm.getelementptr %arg0[%157] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %152, %158 : i64, !llvm.ptr
          %159 = llvm.load %118 : !llvm.ptr -> i64
          %160 = arith.addi %159, %108 : i64
          llvm.store %160, %118 : i64, !llvm.ptr
          %161 = llvm.load %121 : !llvm.ptr -> i64
          %162 = arith.constant 1 : i32
          %164 = arith.extsi %162 : i32 to i64
          %163 = arith.addi %161, %164 : i64
          llvm.store %163, %121 : i64, !llvm.ptr
          cf.br ^bb24
        ^bb26:
        %165 = llvm.load %112 : !llvm.ptr -> i64
        %166 = llvm.load %100 : !llvm.ptr -> i64
        %167 = arith.addi %165, %166 : i64
        llvm.store %167, %112 : i64, !llvm.ptr
        cf.br ^bb21
      ^bb23:
      %168 = llvm.load %100 : !llvm.ptr -> i64
      %169 = arith.constant 1 : i32
      %171 = arith.extsi %169 : i32 to i64
      %170 = arith.shli %168, %171 : i64
      llvm.store %170, %100 : i64, !llvm.ptr
      cf.br ^bb18
    ^bb20:
    %172 = arith.constant 0 : i32
    %173 = arith.cmpi ne, %arg6, %172 : i32
    cf.cond_br %173, ^bb27, ^bb28
    ^bb27:
      %175 = arith.constant 2 : i32
      %177 = arith.extsi %175 : i32 to i64
      %176 = arith.subi %arg2, %177 : i64
      %174 = func.call @mod_pow(%arg1, %176, %arg2) : (i64, i64, i64) -> i64
      %178 = arith.constant 0 : i32
      %179 = arith.extsi %178 : i32 to i64
      %180 = llvm.mlir.constant(1 : i64) : i64
      %181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
      llvm.store %179, %181 : i64, !llvm.ptr
      cf.br ^bb30
      ^bb30:
      %182 = llvm.load %181 : !llvm.ptr -> i64
      %183 = arith.cmpi slt, %182, %arg1 : i64
      cf.cond_br %183, ^bb31, ^bb32
      ^bb31:
        %185 = llvm.load %181 : !llvm.ptr -> i64
        %186 = llvm.getelementptr %arg0[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %184 = llvm.load %186 : !llvm.ptr -> i64
        %187 = arith.extsi %184 : i64 to i128
        %188 = arith.extsi %174 : i64 to i128
        %190 = arith.trunci %187 : i128 to i64
        %191 = arith.trunci %188 : i128 to i64
        %189 = arith.muli %190, %191 : i64
        %192 = arith.extsi %arg2 : i64 to i128
        %194 = arith.trunci %192 : i128 to i64
        %193 = arith.remsi %189, %194 : i64
        %195 = llvm.load %181 : !llvm.ptr -> i64
        %196 = llvm.getelementptr %arg0[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %193, %196 : i64, !llvm.ptr
        %197 = llvm.load %181 : !llvm.ptr -> i64
        %198 = arith.constant 1 : i32
        %200 = arith.extsi %198 : i32 to i64
        %199 = arith.addi %197, %200 : i64
        llvm.store %199, %181 : i64, !llvm.ptr
        cf.br ^bb30
      ^bb32:
      cf.br ^bb29
    ^bb28:
      cf.br ^bb29
    ^bb29:
    func.return
  }
  func.func @ctx_init(%arg0: i64) -> () {
    %201 = llvm.mlir.addressof @g_n : !llvm.ptr
    llvm.store %arg0, %201 : i64, !llvm.ptr
    %203 = arith.constant 4 : i32
    %205 = arith.extsi %203 : i32 to i64
    %204 = arith.muli %arg0, %205 : i64
    %202 = func.call @malloc(%204) : (i64) -> !llvm.ptr
    %206 = llvm.mlir.addressof @g_rev : !llvm.ptr
    llvm.store %202, %206 : !llvm.ptr, !llvm.ptr
    %207 = arith.constant 0 : i32
    %208 = llvm.mlir.constant(1 : i64) : i64
    %209 = llvm.alloca %208 x i32 : (i64) -> !llvm.ptr
    llvm.store %207, %209 : i32, !llvm.ptr
    %210 = arith.constant 1 : i32
    %211 = arith.extsi %210 : i32 to i64
    %212 = llvm.mlir.constant(1 : i64) : i64
    %213 = llvm.alloca %212 x i64 : (i64) -> !llvm.ptr
    llvm.store %211, %213 : i64, !llvm.ptr
    cf.br ^bb33
    ^bb33:
    %214 = llvm.load %213 : !llvm.ptr -> i64
    %215 = arith.cmpi slt, %214, %arg0 : i64
    cf.cond_br %215, ^bb34, ^bb35
    ^bb34:
      %216 = arith.constant 1 : i32
      %218 = arith.extsi %216 : i32 to i64
      %217 = arith.shrsi %arg0, %218 : i64
      %219 = arith.trunci %217 : i64 to i32
      %220 = llvm.mlir.constant(1 : i64) : i64
      %221 = llvm.alloca %220 x i32 : (i64) -> !llvm.ptr
      llvm.store %219, %221 : i32, !llvm.ptr
      cf.br ^bb36
      ^bb36:
      %222 = llvm.load %209 : !llvm.ptr -> i32
      %223 = llvm.load %221 : !llvm.ptr -> i32
      %224 = arith.andi %222, %223 : i32
      %225 = arith.constant 0 : i32
      %226 = arith.cmpi ne, %224, %225 : i32
      cf.cond_br %226, ^bb37, ^bb38
      ^bb37:
        %227 = llvm.load %209 : !llvm.ptr -> i32
        %228 = llvm.load %221 : !llvm.ptr -> i32
        %229 = arith.xori %227, %228 : i32
        llvm.store %229, %209 : i32, !llvm.ptr
        %230 = llvm.load %221 : !llvm.ptr -> i32
        %231 = arith.constant 1 : i32
        %232 = arith.shrsi %230, %231 : i32
        llvm.store %232, %221 : i32, !llvm.ptr
        cf.br ^bb36
      ^bb38:
      %233 = llvm.load %209 : !llvm.ptr -> i32
      %234 = llvm.load %221 : !llvm.ptr -> i32
      %235 = arith.xori %233, %234 : i32
      llvm.store %235, %209 : i32, !llvm.ptr
      %236 = llvm.load %209 : !llvm.ptr -> i32
      %237 = llvm.mlir.addressof @g_rev : !llvm.ptr
      %238 = llvm.load %237 : !llvm.ptr -> !llvm.ptr
      %239 = llvm.load %213 : !llvm.ptr -> i64
      %240 = llvm.getelementptr %238[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %236, %240 : i32, !llvm.ptr
      %241 = llvm.load %213 : !llvm.ptr -> i64
      %242 = arith.constant 1 : i32
      %244 = arith.extsi %242 : i32 to i64
      %243 = arith.addi %241, %244 : i64
      llvm.store %243, %213 : i64, !llvm.ptr
      cf.br ^bb33
    ^bb35:
    %245 = arith.constant 0 : i32
    %246 = llvm.mlir.addressof @g_rev : !llvm.ptr
    %247 = llvm.load %246 : !llvm.ptr -> !llvm.ptr
    %248 = arith.constant 0 : i32
    %249 = arith.extsi %248 : i32 to i64
    %250 = llvm.getelementptr %247[%249] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %245, %250 : i32, !llvm.ptr
    %252 = llvm.mlir.addressof @P1 : !llvm.ptr
    %253 = llvm.load %252 : !llvm.ptr -> i64
    %254 = llvm.mlir.addressof @P2 : !llvm.ptr
    %255 = llvm.load %254 : !llvm.ptr -> i64
    %256 = llvm.mlir.addressof @P3 : !llvm.ptr
    %257 = llvm.load %256 : !llvm.ptr -> i64
    %258 = llvm.mlir.constant(1 : i64) : i64
    %259 = llvm.alloca %258 x !llvm.array<3 x i64> : (i64) -> !llvm.ptr
    %260 = llvm.mlir.zero : !llvm.array<3 x i64>
    llvm.store %260, %259 : !llvm.array<3 x i64>, !llvm.ptr
    %261 = llvm.mlir.constant(0 : i64) : i64
    %262 = llvm.getelementptr %259[0, %261] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %253, %262 : i64, !llvm.ptr
    %263 = llvm.mlir.constant(1 : i64) : i64
    %264 = llvm.getelementptr %259[0, %263] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %255, %264 : i64, !llvm.ptr
    %265 = llvm.mlir.constant(2 : i64) : i64
    %266 = llvm.getelementptr %259[0, %265] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %257, %266 : i64, !llvm.ptr
    %268 = arith.constant 3 : i32
    %269 = arith.constant 3 : i32
    %270 = arith.constant 3 : i32
    %271 = llvm.mlir.constant(1 : i64) : i64
    %272 = llvm.alloca %271 x !llvm.array<3 x i64> : (i64) -> !llvm.ptr
    %273 = llvm.mlir.zero : !llvm.array<3 x i64>
    llvm.store %273, %272 : !llvm.array<3 x i64>, !llvm.ptr
    %274 = arith.extsi %268 : i32 to i64
    %275 = arith.extsi %269 : i32 to i64
    %276 = arith.extsi %270 : i32 to i64
    %277 = llvm.mlir.constant(0 : i64) : i64
    %278 = llvm.getelementptr %272[0, %277] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %274, %278 : i64, !llvm.ptr
    %279 = llvm.mlir.constant(1 : i64) : i64
    %280 = llvm.getelementptr %272[0, %279] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %275, %280 : i64, !llvm.ptr
    %281 = llvm.mlir.constant(2 : i64) : i64
    %282 = llvm.getelementptr %272[0, %281] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %276, %282 : i64, !llvm.ptr
    %284 = arith.constant 8 : i32
    %286 = arith.extsi %284 : i32 to i64
    %285 = arith.muli %arg0, %286 : i64
    %283 = func.call @malloc(%285) : (i64) -> !llvm.ptr
    %287 = llvm.mlir.addressof @g_roots0 : !llvm.ptr
    llvm.store %283, %287 : !llvm.ptr, !llvm.ptr
    %289 = arith.constant 8 : i32
    %291 = arith.extsi %289 : i32 to i64
    %290 = arith.muli %arg0, %291 : i64
    %288 = func.call @malloc(%290) : (i64) -> !llvm.ptr
    %292 = llvm.mlir.addressof @g_roots_inv0 : !llvm.ptr
    llvm.store %288, %292 : !llvm.ptr, !llvm.ptr
    %294 = arith.constant 8 : i32
    %296 = arith.extsi %294 : i32 to i64
    %295 = arith.muli %arg0, %296 : i64
    %293 = func.call @malloc(%295) : (i64) -> !llvm.ptr
    %297 = llvm.mlir.addressof @g_roots1 : !llvm.ptr
    llvm.store %293, %297 : !llvm.ptr, !llvm.ptr
    %299 = arith.constant 8 : i32
    %301 = arith.extsi %299 : i32 to i64
    %300 = arith.muli %arg0, %301 : i64
    %298 = func.call @malloc(%300) : (i64) -> !llvm.ptr
    %302 = llvm.mlir.addressof @g_roots_inv1 : !llvm.ptr
    llvm.store %298, %302 : !llvm.ptr, !llvm.ptr
    %304 = arith.constant 8 : i32
    %306 = arith.extsi %304 : i32 to i64
    %305 = arith.muli %arg0, %306 : i64
    %303 = func.call @malloc(%305) : (i64) -> !llvm.ptr
    %307 = llvm.mlir.addressof @g_roots2 : !llvm.ptr
    llvm.store %303, %307 : !llvm.ptr, !llvm.ptr
    %309 = arith.constant 8 : i32
    %311 = arith.extsi %309 : i32 to i64
    %310 = arith.muli %arg0, %311 : i64
    %308 = func.call @malloc(%310) : (i64) -> !llvm.ptr
    %312 = llvm.mlir.addressof @g_roots_inv2 : !llvm.ptr
    llvm.store %308, %312 : !llvm.ptr, !llvm.ptr
    %314 = llvm.mlir.addressof @g_roots0 : !llvm.ptr
    %315 = llvm.load %314 : !llvm.ptr -> !llvm.ptr
    %316 = llvm.mlir.addressof @g_roots1 : !llvm.ptr
    %317 = llvm.load %316 : !llvm.ptr -> !llvm.ptr
    %318 = llvm.mlir.addressof @g_roots2 : !llvm.ptr
    %319 = llvm.load %318 : !llvm.ptr -> !llvm.ptr
    %320 = llvm.mlir.constant(1 : i64) : i64
    %321 = llvm.alloca %320 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %322 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %322, %321 : !llvm.array<3 x ptr>, !llvm.ptr
    %323 = llvm.mlir.constant(0 : i64) : i64
    %324 = llvm.getelementptr %321[0, %323] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %315, %324 : !llvm.ptr, !llvm.ptr
    %325 = llvm.mlir.constant(1 : i64) : i64
    %326 = llvm.getelementptr %321[0, %325] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %317, %326 : !llvm.ptr, !llvm.ptr
    %327 = llvm.mlir.constant(2 : i64) : i64
    %328 = llvm.getelementptr %321[0, %327] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %319, %328 : !llvm.ptr, !llvm.ptr
    %330 = llvm.mlir.addressof @g_roots_inv0 : !llvm.ptr
    %331 = llvm.load %330 : !llvm.ptr -> !llvm.ptr
    %332 = llvm.mlir.addressof @g_roots_inv1 : !llvm.ptr
    %333 = llvm.load %332 : !llvm.ptr -> !llvm.ptr
    %334 = llvm.mlir.addressof @g_roots_inv2 : !llvm.ptr
    %335 = llvm.load %334 : !llvm.ptr -> !llvm.ptr
    %336 = llvm.mlir.constant(1 : i64) : i64
    %337 = llvm.alloca %336 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %338 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %338, %337 : !llvm.array<3 x ptr>, !llvm.ptr
    %339 = llvm.mlir.constant(0 : i64) : i64
    %340 = llvm.getelementptr %337[0, %339] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %331, %340 : !llvm.ptr, !llvm.ptr
    %341 = llvm.mlir.constant(1 : i64) : i64
    %342 = llvm.getelementptr %337[0, %341] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %333, %342 : !llvm.ptr, !llvm.ptr
    %343 = llvm.mlir.constant(2 : i64) : i64
    %344 = llvm.getelementptr %337[0, %343] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %335, %344 : !llvm.ptr, !llvm.ptr
    %345 = arith.constant 0 : i32
    %346 = llvm.mlir.constant(1 : i64) : i64
    %347 = llvm.alloca %346 x i32 : (i64) -> !llvm.ptr
    llvm.store %345, %347 : i32, !llvm.ptr
    cf.br ^bb39
    ^bb39:
    %348 = llvm.load %347 : !llvm.ptr -> i32
    %349 = arith.constant 3 : i32
    %350 = arith.cmpi slt, %348, %349 : i32
    cf.cond_br %350, ^bb40, ^bb41
    ^bb40:
      %352 = llvm.load %347 : !llvm.ptr -> i32
      %353 = arith.extsi %352 : i32 to i64
      %354 = llvm.getelementptr %259[0, %353] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
      %351 = llvm.load %354 : !llvm.ptr -> i64
      %356 = llvm.load %347 : !llvm.ptr -> i32
      %357 = arith.extsi %356 : i32 to i64
      %358 = llvm.getelementptr %272[0, %357] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
      %355 = llvm.load %358 : !llvm.ptr -> i64
      %360 = arith.constant 1 : i32
      %362 = arith.extsi %360 : i32 to i64
      %361 = arith.subi %351, %362 : i64
      %363 = arith.divsi %361, %arg0 : i64
      %359 = func.call @mod_pow(%355, %363, %351) : (i64, i64, i64) -> i64
      %365 = arith.constant 2 : i32
      %367 = arith.extsi %365 : i32 to i64
      %366 = arith.subi %351, %367 : i64
      %364 = func.call @mod_pow(%359, %366, %351) : (i64, i64, i64) -> i64
      %369 = llvm.load %347 : !llvm.ptr -> i32
      %370 = arith.extsi %369 : i32 to i64
      %371 = llvm.getelementptr %321[0, %370] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %368 = llvm.load %371 : !llvm.ptr -> !llvm.ptr
      %373 = llvm.load %347 : !llvm.ptr -> i32
      %374 = arith.extsi %373 : i32 to i64
      %375 = llvm.getelementptr %337[0, %374] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %372 = llvm.load %375 : !llvm.ptr -> !llvm.ptr
      %376 = arith.constant 1 : i32
      %377 = arith.constant 0 : i32
      %378 = arith.extsi %376 : i32 to i64
      %379 = arith.extsi %377 : i32 to i64
      %380 = llvm.getelementptr %368[%379] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %378, %380 : i64, !llvm.ptr
      %381 = arith.constant 1 : i32
      %382 = arith.constant 0 : i32
      %383 = arith.extsi %381 : i32 to i64
      %384 = arith.extsi %382 : i32 to i64
      %385 = llvm.getelementptr %372[%384] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %383, %385 : i64, !llvm.ptr
      %386 = arith.constant 1 : i32
      %387 = arith.extsi %386 : i32 to i64
      %388 = llvm.mlir.constant(1 : i64) : i64
      %389 = llvm.alloca %388 x i64 : (i64) -> !llvm.ptr
      llvm.store %387, %389 : i64, !llvm.ptr
      cf.br ^bb42
      ^bb42:
      %390 = llvm.load %389 : !llvm.ptr -> i64
      %391 = arith.cmpi slt, %390, %arg0 : i64
      cf.cond_br %391, ^bb43, ^bb44
      ^bb43:
        %393 = llvm.load %389 : !llvm.ptr -> i64
        %394 = arith.constant 1 : i32
        %396 = arith.extsi %394 : i32 to i64
        %395 = arith.subi %393, %396 : i64
        %397 = llvm.getelementptr %368[%395] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %392 = llvm.load %397 : !llvm.ptr -> i64
        %398 = arith.extsi %392 : i64 to i128
        %399 = arith.extsi %359 : i64 to i128
        %401 = arith.trunci %398 : i128 to i64
        %402 = arith.trunci %399 : i128 to i64
        %400 = arith.muli %401, %402 : i64
        %403 = arith.extsi %351 : i64 to i128
        %405 = arith.trunci %403 : i128 to i64
        %404 = arith.remsi %400, %405 : i64
        %406 = llvm.load %389 : !llvm.ptr -> i64
        %407 = llvm.getelementptr %368[%406] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %404, %407 : i64, !llvm.ptr
        %409 = llvm.load %389 : !llvm.ptr -> i64
        %410 = arith.constant 1 : i32
        %412 = arith.extsi %410 : i32 to i64
        %411 = arith.subi %409, %412 : i64
        %413 = llvm.getelementptr %372[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %408 = llvm.load %413 : !llvm.ptr -> i64
        %414 = arith.extsi %408 : i64 to i128
        %415 = arith.extsi %364 : i64 to i128
        %417 = arith.trunci %414 : i128 to i64
        %418 = arith.trunci %415 : i128 to i64
        %416 = arith.muli %417, %418 : i64
        %419 = arith.extsi %351 : i64 to i128
        %421 = arith.trunci %419 : i128 to i64
        %420 = arith.remsi %416, %421 : i64
        %422 = llvm.load %389 : !llvm.ptr -> i64
        %423 = llvm.getelementptr %372[%422] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %420, %423 : i64, !llvm.ptr
        %424 = llvm.load %389 : !llvm.ptr -> i64
        %425 = arith.constant 1 : i32
        %427 = arith.extsi %425 : i32 to i64
        %426 = arith.addi %424, %427 : i64
        llvm.store %426, %389 : i64, !llvm.ptr
        cf.br ^bb42
      ^bb44:
      %428 = llvm.load %347 : !llvm.ptr -> i32
      %429 = arith.constant 1 : i32
      %430 = arith.addi %428, %429 : i32
      llvm.store %430, %347 : i32, !llvm.ptr
      cf.br ^bb39
    ^bb41:
    %432 = llvm.mlir.addressof @P1 : !llvm.ptr
    %433 = llvm.load %432 : !llvm.ptr -> i64
    %434 = llvm.mlir.addressof @P2 : !llvm.ptr
    %435 = llvm.load %434 : !llvm.ptr -> i64
    %436 = arith.constant 2 : i32
    %438 = arith.extsi %436 : i32 to i64
    %437 = arith.subi %435, %438 : i64
    %439 = llvm.mlir.addressof @P2 : !llvm.ptr
    %440 = llvm.load %439 : !llvm.ptr -> i64
    %431 = func.call @mod_pow(%433, %437, %440) : (i64, i64, i64) -> i64
    %441 = llvm.mlir.addressof @g_inv_p1_mod_p2 : !llvm.ptr
    llvm.store %431, %441 : i64, !llvm.ptr
    %442 = llvm.mlir.addressof @P1 : !llvm.ptr
    %443 = llvm.load %442 : !llvm.ptr -> i64
    %444 = llvm.mlir.addressof @P3 : !llvm.ptr
    %445 = llvm.load %444 : !llvm.ptr -> i64
    %446 = arith.remsi %443, %445 : i64
    %447 = llvm.mlir.addressof @g_p1_mod_p3 : !llvm.ptr
    llvm.store %446, %447 : i64, !llvm.ptr
    %448 = llvm.mlir.addressof @P1 : !llvm.ptr
    %449 = llvm.load %448 : !llvm.ptr -> i64
    %450 = arith.extsi %449 : i64 to i128
    %451 = llvm.mlir.addressof @P2 : !llvm.ptr
    %452 = llvm.load %451 : !llvm.ptr -> i64
    %453 = arith.extsi %452 : i64 to i128
    %455 = arith.trunci %450 : i128 to i64
    %456 = arith.trunci %453 : i128 to i64
    %454 = arith.muli %455, %456 : i64
    %457 = llvm.mlir.addressof @P3 : !llvm.ptr
    %458 = llvm.load %457 : !llvm.ptr -> i64
    %459 = arith.extsi %458 : i64 to i128
    %461 = arith.trunci %459 : i128 to i64
    %460 = arith.remsi %454, %461 : i64
    %462 = llvm.mlir.addressof @g_p12_mod_p3 : !llvm.ptr
    llvm.store %460, %462 : i64, !llvm.ptr
    %464 = llvm.mlir.addressof @g_p12_mod_p3 : !llvm.ptr
    %465 = llvm.load %464 : !llvm.ptr -> i64
    %466 = llvm.mlir.addressof @P3 : !llvm.ptr
    %467 = llvm.load %466 : !llvm.ptr -> i64
    %468 = arith.constant 2 : i32
    %470 = arith.extsi %468 : i32 to i64
    %469 = arith.subi %467, %470 : i64
    %471 = llvm.mlir.addressof @P3 : !llvm.ptr
    %472 = llvm.load %471 : !llvm.ptr -> i64
    %463 = func.call @mod_pow(%465, %469, %472) : (i64, i64, i64) -> i64
    %473 = llvm.mlir.addressof @g_inv_p12_mod_p3 : !llvm.ptr
    llvm.store %463, %473 : i64, !llvm.ptr
    %474 = llvm.mlir.addressof @P1 : !llvm.ptr
    %475 = llvm.load %474 : !llvm.ptr -> i64
    %476 = llvm.mlir.addressof @MOD : !llvm.ptr
    %477 = llvm.load %476 : !llvm.ptr -> i64
    %478 = arith.remsi %475, %477 : i64
    %479 = llvm.mlir.addressof @g_p1_mod_mod : !llvm.ptr
    llvm.store %478, %479 : i64, !llvm.ptr
    %480 = llvm.mlir.addressof @P1 : !llvm.ptr
    %481 = llvm.load %480 : !llvm.ptr -> i64
    %482 = arith.extsi %481 : i64 to i128
    %483 = llvm.mlir.addressof @P2 : !llvm.ptr
    %484 = llvm.load %483 : !llvm.ptr -> i64
    %485 = arith.extsi %484 : i64 to i128
    %487 = arith.trunci %482 : i128 to i64
    %488 = arith.trunci %485 : i128 to i64
    %486 = arith.muli %487, %488 : i64
    %489 = llvm.mlir.addressof @MOD : !llvm.ptr
    %490 = llvm.load %489 : !llvm.ptr -> i64
    %491 = arith.extsi %490 : i64 to i128
    %493 = arith.trunci %491 : i128 to i64
    %492 = arith.remsi %486, %493 : i64
    %494 = llvm.mlir.addressof @g_p12_mod_mod : !llvm.ptr
    llvm.store %492, %494 : i64, !llvm.ptr
    func.return
  }
  func.func @ctx_free() -> () {
    %496 = llvm.mlir.addressof @g_rev : !llvm.ptr
    %497 = llvm.load %496 : !llvm.ptr -> !llvm.ptr
    func.call @free(%497) : (!llvm.ptr) -> ()
    %499 = llvm.mlir.addressof @g_roots0 : !llvm.ptr
    %500 = llvm.load %499 : !llvm.ptr -> !llvm.ptr
    func.call @free(%500) : (!llvm.ptr) -> ()
    %502 = llvm.mlir.addressof @g_roots_inv0 : !llvm.ptr
    %503 = llvm.load %502 : !llvm.ptr -> !llvm.ptr
    func.call @free(%503) : (!llvm.ptr) -> ()
    %505 = llvm.mlir.addressof @g_roots1 : !llvm.ptr
    %506 = llvm.load %505 : !llvm.ptr -> !llvm.ptr
    func.call @free(%506) : (!llvm.ptr) -> ()
    %508 = llvm.mlir.addressof @g_roots_inv1 : !llvm.ptr
    %509 = llvm.load %508 : !llvm.ptr -> !llvm.ptr
    func.call @free(%509) : (!llvm.ptr) -> ()
    %511 = llvm.mlir.addressof @g_roots2 : !llvm.ptr
    %512 = llvm.load %511 : !llvm.ptr -> !llvm.ptr
    func.call @free(%512) : (!llvm.ptr) -> ()
    %514 = llvm.mlir.addressof @g_roots_inv2 : !llvm.ptr
    %515 = llvm.load %514 : !llvm.ptr -> !llvm.ptr
    func.call @free(%515) : (!llvm.ptr) -> ()
    func.return
  }
  func.func @crt_reduce(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i64) -> () {
    %516 = arith.constant 0 : i32
    %517 = arith.extsi %516 : i32 to i64
    %518 = llvm.mlir.constant(1 : i64) : i64
    %519 = llvm.alloca %518 x i64 : (i64) -> !llvm.ptr
    llvm.store %517, %519 : i64, !llvm.ptr
    cf.br ^bb45
    ^bb45:
    %520 = llvm.load %519 : !llvm.ptr -> i64
    %521 = arith.cmpi slt, %520, %arg4 : i64
    cf.cond_br %521, ^bb46, ^bb47
    ^bb46:
      %523 = llvm.load %519 : !llvm.ptr -> i64
      %524 = llvm.getelementptr %arg1[%523] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %522 = llvm.load %524 : !llvm.ptr -> i64
      %526 = llvm.load %519 : !llvm.ptr -> i64
      %527 = llvm.getelementptr %arg2[%526] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %525 = llvm.load %527 : !llvm.ptr -> i64
      %529 = llvm.load %519 : !llvm.ptr -> i64
      %530 = llvm.getelementptr %arg3[%529] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %528 = llvm.load %530 : !llvm.ptr -> i64
      %531 = arith.subi %525, %522 : i64
      %532 = llvm.mlir.addressof @P2 : !llvm.ptr
      %533 = llvm.load %532 : !llvm.ptr -> i64
      %534 = arith.remsi %531, %533 : i64
      %535 = llvm.mlir.addressof @P2 : !llvm.ptr
      %536 = llvm.load %535 : !llvm.ptr -> i64
      %537 = arith.addi %534, %536 : i64
      %538 = llvm.mlir.addressof @P2 : !llvm.ptr
      %539 = llvm.load %538 : !llvm.ptr -> i64
      %540 = arith.remsi %537, %539 : i64
      %541 = arith.extsi %540 : i64 to i128
      %542 = llvm.mlir.addressof @g_inv_p1_mod_p2 : !llvm.ptr
      %543 = llvm.load %542 : !llvm.ptr -> i64
      %544 = arith.extsi %543 : i64 to i128
      %546 = arith.trunci %541 : i128 to i64
      %547 = arith.trunci %544 : i128 to i64
      %545 = arith.muli %546, %547 : i64
      %548 = llvm.mlir.addressof @P2 : !llvm.ptr
      %549 = llvm.load %548 : !llvm.ptr -> i64
      %550 = arith.extsi %549 : i64 to i128
      %552 = arith.trunci %550 : i128 to i64
      %551 = arith.remsi %545, %552 : i64
      %553 = llvm.mlir.addressof @g_p1_mod_p3 : !llvm.ptr
      %554 = llvm.load %553 : !llvm.ptr -> i64
      %555 = arith.extsi %554 : i64 to i128
      %556 = arith.extsi %551 : i64 to i128
      %558 = arith.trunci %555 : i128 to i64
      %559 = arith.trunci %556 : i128 to i64
      %557 = arith.muli %558, %559 : i64
      %560 = llvm.mlir.addressof @P3 : !llvm.ptr
      %561 = llvm.load %560 : !llvm.ptr -> i64
      %562 = arith.extsi %561 : i64 to i128
      %564 = arith.trunci %562 : i128 to i64
      %563 = arith.remsi %557, %564 : i64
      %565 = arith.addi %522, %563 : i64
      %566 = llvm.mlir.addressof @P3 : !llvm.ptr
      %567 = llvm.load %566 : !llvm.ptr -> i64
      %568 = arith.remsi %565, %567 : i64
      %569 = arith.subi %528, %568 : i64
      %570 = llvm.mlir.addressof @P3 : !llvm.ptr
      %571 = llvm.load %570 : !llvm.ptr -> i64
      %572 = arith.remsi %569, %571 : i64
      %573 = llvm.mlir.addressof @P3 : !llvm.ptr
      %574 = llvm.load %573 : !llvm.ptr -> i64
      %575 = arith.addi %572, %574 : i64
      %576 = llvm.mlir.addressof @P3 : !llvm.ptr
      %577 = llvm.load %576 : !llvm.ptr -> i64
      %578 = arith.remsi %575, %577 : i64
      %579 = arith.extsi %578 : i64 to i128
      %580 = llvm.mlir.addressof @g_inv_p12_mod_p3 : !llvm.ptr
      %581 = llvm.load %580 : !llvm.ptr -> i64
      %582 = arith.extsi %581 : i64 to i128
      %584 = arith.trunci %579 : i128 to i64
      %585 = arith.trunci %582 : i128 to i64
      %583 = arith.muli %584, %585 : i64
      %586 = llvm.mlir.addressof @P3 : !llvm.ptr
      %587 = llvm.load %586 : !llvm.ptr -> i64
      %588 = arith.extsi %587 : i64 to i128
      %590 = arith.trunci %588 : i128 to i64
      %589 = arith.remsi %583, %590 : i64
      %591 = llvm.mlir.addressof @g_p1_mod_mod : !llvm.ptr
      %592 = llvm.load %591 : !llvm.ptr -> i64
      %593 = arith.extsi %592 : i64 to i128
      %594 = llvm.mlir.addressof @MOD : !llvm.ptr
      %595 = llvm.load %594 : !llvm.ptr -> i64
      %596 = arith.extsi %595 : i64 to i128
      %598 = arith.trunci %596 : i128 to i64
      %597 = arith.remsi %551, %598 : i64
      %600 = arith.trunci %593 : i128 to i64
      %599 = arith.muli %600, %597 : i64
      %601 = llvm.mlir.addressof @MOD : !llvm.ptr
      %602 = llvm.load %601 : !llvm.ptr -> i64
      %603 = arith.extsi %602 : i64 to i128
      %605 = arith.trunci %603 : i128 to i64
      %604 = arith.remsi %599, %605 : i64
      %606 = arith.addi %522, %604 : i64
      %607 = llvm.mlir.addressof @g_p12_mod_mod : !llvm.ptr
      %608 = llvm.load %607 : !llvm.ptr -> i64
      %609 = arith.extsi %608 : i64 to i128
      %610 = llvm.mlir.addressof @MOD : !llvm.ptr
      %611 = llvm.load %610 : !llvm.ptr -> i64
      %612 = arith.extsi %611 : i64 to i128
      %614 = arith.trunci %612 : i128 to i64
      %613 = arith.remsi %589, %614 : i64
      %616 = arith.trunci %609 : i128 to i64
      %615 = arith.muli %616, %613 : i64
      %617 = llvm.mlir.addressof @MOD : !llvm.ptr
      %618 = llvm.load %617 : !llvm.ptr -> i64
      %619 = arith.extsi %618 : i64 to i128
      %621 = arith.trunci %619 : i128 to i64
      %620 = arith.remsi %615, %621 : i64
      %622 = arith.addi %606, %620 : i64
      %623 = llvm.mlir.addressof @MOD : !llvm.ptr
      %624 = llvm.load %623 : !llvm.ptr -> i64
      %625 = arith.remsi %622, %624 : i64
      %626 = llvm.load %519 : !llvm.ptr -> i64
      %627 = llvm.getelementptr %arg0[%626] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %625, %627 : i64, !llvm.ptr
      %628 = llvm.load %519 : !llvm.ptr -> i64
      %629 = arith.constant 1 : i32
      %631 = arith.extsi %629 : i32 to i64
      %630 = arith.addi %628, %631 : i64
      llvm.store %630, %519 : i64, !llvm.ptr
      cf.br ^bb45
    ^bb47:
    func.return
  }
  func.func @convolution_mod(%arg0: !llvm.ptr, %arg1: i64, %arg2: !llvm.ptr, %arg3: i64) -> !llvm.ptr {
    %632 = arith.addi %arg1, %arg3 : i64
    %633 = arith.constant 1 : i32
    %635 = arith.extsi %633 : i32 to i64
    %634 = arith.subi %632, %635 : i64
    %636 = llvm.mlir.addressof @g_n : !llvm.ptr
    %637 = llvm.load %636 : !llvm.ptr -> i64
    %639 = llvm.mlir.addressof @P1 : !llvm.ptr
    %640 = llvm.load %639 : !llvm.ptr -> i64
    %641 = llvm.mlir.addressof @P2 : !llvm.ptr
    %642 = llvm.load %641 : !llvm.ptr -> i64
    %643 = llvm.mlir.addressof @P3 : !llvm.ptr
    %644 = llvm.load %643 : !llvm.ptr -> i64
    %645 = llvm.mlir.constant(1 : i64) : i64
    %646 = llvm.alloca %645 x !llvm.array<3 x i64> : (i64) -> !llvm.ptr
    %647 = llvm.mlir.zero : !llvm.array<3 x i64>
    llvm.store %647, %646 : !llvm.array<3 x i64>, !llvm.ptr
    %648 = llvm.mlir.constant(0 : i64) : i64
    %649 = llvm.getelementptr %646[0, %648] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %640, %649 : i64, !llvm.ptr
    %650 = llvm.mlir.constant(1 : i64) : i64
    %651 = llvm.getelementptr %646[0, %650] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %642, %651 : i64, !llvm.ptr
    %652 = llvm.mlir.constant(2 : i64) : i64
    %653 = llvm.getelementptr %646[0, %652] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %644, %653 : i64, !llvm.ptr
    %655 = llvm.mlir.addressof @g_roots0 : !llvm.ptr
    %656 = llvm.load %655 : !llvm.ptr -> !llvm.ptr
    %657 = llvm.mlir.addressof @g_roots1 : !llvm.ptr
    %658 = llvm.load %657 : !llvm.ptr -> !llvm.ptr
    %659 = llvm.mlir.addressof @g_roots2 : !llvm.ptr
    %660 = llvm.load %659 : !llvm.ptr -> !llvm.ptr
    %661 = llvm.mlir.constant(1 : i64) : i64
    %662 = llvm.alloca %661 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %663 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %663, %662 : !llvm.array<3 x ptr>, !llvm.ptr
    %664 = llvm.mlir.constant(0 : i64) : i64
    %665 = llvm.getelementptr %662[0, %664] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %656, %665 : !llvm.ptr, !llvm.ptr
    %666 = llvm.mlir.constant(1 : i64) : i64
    %667 = llvm.getelementptr %662[0, %666] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %658, %667 : !llvm.ptr, !llvm.ptr
    %668 = llvm.mlir.constant(2 : i64) : i64
    %669 = llvm.getelementptr %662[0, %668] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %660, %669 : !llvm.ptr, !llvm.ptr
    %671 = llvm.mlir.addressof @g_roots_inv0 : !llvm.ptr
    %672 = llvm.load %671 : !llvm.ptr -> !llvm.ptr
    %673 = llvm.mlir.addressof @g_roots_inv1 : !llvm.ptr
    %674 = llvm.load %673 : !llvm.ptr -> !llvm.ptr
    %675 = llvm.mlir.addressof @g_roots_inv2 : !llvm.ptr
    %676 = llvm.load %675 : !llvm.ptr -> !llvm.ptr
    %677 = llvm.mlir.constant(1 : i64) : i64
    %678 = llvm.alloca %677 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %679 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %679, %678 : !llvm.array<3 x ptr>, !llvm.ptr
    %680 = llvm.mlir.constant(0 : i64) : i64
    %681 = llvm.getelementptr %678[0, %680] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %672, %681 : !llvm.ptr, !llvm.ptr
    %682 = llvm.mlir.constant(1 : i64) : i64
    %683 = llvm.getelementptr %678[0, %682] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %674, %683 : !llvm.ptr, !llvm.ptr
    %684 = llvm.mlir.constant(2 : i64) : i64
    %685 = llvm.getelementptr %678[0, %684] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %676, %685 : !llvm.ptr, !llvm.ptr
    %687 = arith.constant 8 : i32
    %689 = arith.extsi %687 : i32 to i64
    %688 = arith.muli %634, %689 : i64
    %686 = func.call @malloc(%688) : (i64) -> !llvm.ptr
    %691 = arith.constant 8 : i32
    %693 = arith.extsi %691 : i32 to i64
    %692 = arith.muli %634, %693 : i64
    %690 = func.call @malloc(%692) : (i64) -> !llvm.ptr
    %695 = arith.constant 8 : i32
    %697 = arith.extsi %695 : i32 to i64
    %696 = arith.muli %634, %697 : i64
    %694 = func.call @malloc(%696) : (i64) -> !llvm.ptr
    %699 = llvm.mlir.constant(1 : i64) : i64
    %700 = llvm.alloca %699 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %701 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %701, %700 : !llvm.array<3 x ptr>, !llvm.ptr
    %702 = llvm.mlir.constant(0 : i64) : i64
    %703 = llvm.getelementptr %700[0, %702] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %686, %703 : !llvm.ptr, !llvm.ptr
    %704 = llvm.mlir.constant(1 : i64) : i64
    %705 = llvm.getelementptr %700[0, %704] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %690, %705 : !llvm.ptr, !llvm.ptr
    %706 = llvm.mlir.constant(2 : i64) : i64
    %707 = llvm.getelementptr %700[0, %706] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %694, %707 : !llvm.ptr, !llvm.ptr
    %708 = arith.constant 0 : i32
    %709 = llvm.mlir.constant(1 : i64) : i64
    %710 = llvm.alloca %709 x i32 : (i64) -> !llvm.ptr
    llvm.store %708, %710 : i32, !llvm.ptr
    cf.br ^bb48
    ^bb48:
    %711 = llvm.load %710 : !llvm.ptr -> i32
    %712 = arith.constant 3 : i32
    %713 = arith.cmpi slt, %711, %712 : i32
    cf.cond_br %713, ^bb49, ^bb50
    ^bb49:
      %715 = llvm.load %710 : !llvm.ptr -> i32
      %716 = arith.extsi %715 : i32 to i64
      %717 = llvm.getelementptr %646[0, %716] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
      %714 = llvm.load %717 : !llvm.ptr -> i64
      %719 = arith.constant 8 : i32
      %720 = arith.extsi %719 : i32 to i64
      %718 = func.call @calloc(%637, %720) : (i64, i64) -> !llvm.ptr
      %722 = arith.constant 8 : i32
      %723 = arith.extsi %722 : i32 to i64
      %721 = func.call @calloc(%637, %723) : (i64, i64) -> !llvm.ptr
      %724 = arith.constant 0 : i32
      %725 = arith.extsi %724 : i32 to i64
      %726 = llvm.mlir.constant(1 : i64) : i64
      %727 = llvm.alloca %726 x i64 : (i64) -> !llvm.ptr
      llvm.store %725, %727 : i64, !llvm.ptr
      cf.br ^bb51
      ^bb51:
      %728 = llvm.load %727 : !llvm.ptr -> i64
      %729 = arith.cmpi slt, %728, %arg1 : i64
      cf.cond_br %729, ^bb52, ^bb53
      ^bb52:
        %731 = llvm.load %727 : !llvm.ptr -> i64
        %732 = llvm.getelementptr %arg0[%731] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %730 = llvm.load %732 : !llvm.ptr -> i64
        %733 = arith.remsi %730, %714 : i64
        %734 = arith.addi %733, %714 : i64
        %735 = arith.remsi %734, %714 : i64
        %736 = llvm.load %727 : !llvm.ptr -> i64
        %737 = llvm.getelementptr %718[%736] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %735, %737 : i64, !llvm.ptr
        %738 = llvm.load %727 : !llvm.ptr -> i64
        %739 = arith.constant 1 : i32
        %741 = arith.extsi %739 : i32 to i64
        %740 = arith.addi %738, %741 : i64
        llvm.store %740, %727 : i64, !llvm.ptr
        cf.br ^bb51
      ^bb53:
      %742 = arith.constant 0 : i32
      %743 = arith.extsi %742 : i32 to i64
      llvm.store %743, %727 : i64, !llvm.ptr
      cf.br ^bb54
      ^bb54:
      %744 = llvm.load %727 : !llvm.ptr -> i64
      %745 = arith.cmpi slt, %744, %arg3 : i64
      cf.cond_br %745, ^bb55, ^bb56
      ^bb55:
        %747 = llvm.load %727 : !llvm.ptr -> i64
        %748 = llvm.getelementptr %arg2[%747] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %746 = llvm.load %748 : !llvm.ptr -> i64
        %749 = arith.remsi %746, %714 : i64
        %750 = arith.addi %749, %714 : i64
        %751 = arith.remsi %750, %714 : i64
        %752 = llvm.load %727 : !llvm.ptr -> i64
        %753 = llvm.getelementptr %721[%752] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %751, %753 : i64, !llvm.ptr
        %754 = llvm.load %727 : !llvm.ptr -> i64
        %755 = arith.constant 1 : i32
        %757 = arith.extsi %755 : i32 to i64
        %756 = arith.addi %754, %757 : i64
        llvm.store %756, %727 : i64, !llvm.ptr
        cf.br ^bb54
      ^bb56:
      %760 = llvm.load %710 : !llvm.ptr -> i32
      %761 = arith.extsi %760 : i32 to i64
      %762 = llvm.getelementptr %662[0, %761] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %759 = llvm.load %762 : !llvm.ptr -> !llvm.ptr
      %764 = llvm.load %710 : !llvm.ptr -> i32
      %765 = arith.extsi %764 : i32 to i64
      %766 = llvm.getelementptr %678[0, %765] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %763 = llvm.load %766 : !llvm.ptr -> !llvm.ptr
      %767 = llvm.mlir.addressof @g_rev : !llvm.ptr
      %768 = llvm.load %767 : !llvm.ptr -> !llvm.ptr
      %769 = arith.constant 0 : i32
      func.call @ntt(%718, %637, %714, %759, %763, %768, %769) : (!llvm.ptr, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      %772 = llvm.load %710 : !llvm.ptr -> i32
      %773 = arith.extsi %772 : i32 to i64
      %774 = llvm.getelementptr %662[0, %773] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %771 = llvm.load %774 : !llvm.ptr -> !llvm.ptr
      %776 = llvm.load %710 : !llvm.ptr -> i32
      %777 = arith.extsi %776 : i32 to i64
      %778 = llvm.getelementptr %678[0, %777] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %775 = llvm.load %778 : !llvm.ptr -> !llvm.ptr
      %779 = llvm.mlir.addressof @g_rev : !llvm.ptr
      %780 = llvm.load %779 : !llvm.ptr -> !llvm.ptr
      %781 = arith.constant 0 : i32
      func.call @ntt(%721, %637, %714, %771, %775, %780, %781) : (!llvm.ptr, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      %782 = arith.constant 0 : i32
      %783 = arith.extsi %782 : i32 to i64
      llvm.store %783, %727 : i64, !llvm.ptr
      cf.br ^bb57
      ^bb57:
      %784 = llvm.load %727 : !llvm.ptr -> i64
      %785 = arith.cmpi slt, %784, %637 : i64
      cf.cond_br %785, ^bb58, ^bb59
      ^bb58:
        %787 = llvm.load %727 : !llvm.ptr -> i64
        %788 = llvm.getelementptr %718[%787] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %786 = llvm.load %788 : !llvm.ptr -> i64
        %789 = arith.extsi %786 : i64 to i128
        %791 = llvm.load %727 : !llvm.ptr -> i64
        %792 = llvm.getelementptr %721[%791] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %790 = llvm.load %792 : !llvm.ptr -> i64
        %793 = arith.extsi %790 : i64 to i128
        %795 = arith.trunci %789 : i128 to i64
        %796 = arith.trunci %793 : i128 to i64
        %794 = arith.muli %795, %796 : i64
        %797 = arith.extsi %714 : i64 to i128
        %799 = arith.trunci %797 : i128 to i64
        %798 = arith.remsi %794, %799 : i64
        %800 = llvm.load %727 : !llvm.ptr -> i64
        %801 = llvm.getelementptr %718[%800] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %798, %801 : i64, !llvm.ptr
        %802 = llvm.load %727 : !llvm.ptr -> i64
        %803 = arith.constant 1 : i32
        %805 = arith.extsi %803 : i32 to i64
        %804 = arith.addi %802, %805 : i64
        llvm.store %804, %727 : i64, !llvm.ptr
        cf.br ^bb57
      ^bb59:
      %808 = llvm.load %710 : !llvm.ptr -> i32
      %809 = arith.extsi %808 : i32 to i64
      %810 = llvm.getelementptr %662[0, %809] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %807 = llvm.load %810 : !llvm.ptr -> !llvm.ptr
      %812 = llvm.load %710 : !llvm.ptr -> i32
      %813 = arith.extsi %812 : i32 to i64
      %814 = llvm.getelementptr %678[0, %813] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %811 = llvm.load %814 : !llvm.ptr -> !llvm.ptr
      %815 = llvm.mlir.addressof @g_rev : !llvm.ptr
      %816 = llvm.load %815 : !llvm.ptr -> !llvm.ptr
      %817 = arith.constant 1 : i32
      func.call @ntt(%718, %637, %714, %807, %811, %816, %817) : (!llvm.ptr, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      %820 = llvm.load %710 : !llvm.ptr -> i32
      %821 = arith.extsi %820 : i32 to i64
      %822 = llvm.getelementptr %700[0, %821] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %819 = llvm.load %822 : !llvm.ptr -> !llvm.ptr
      %823 = arith.constant 8 : i32
      %825 = arith.extsi %823 : i32 to i64
      %824 = arith.muli %634, %825 : i64
      %818 = func.call @memcpy(%819, %718, %824) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
      func.call @free(%718) : (!llvm.ptr) -> ()
      func.call @free(%721) : (!llvm.ptr) -> ()
      %828 = llvm.load %710 : !llvm.ptr -> i32
      %829 = arith.constant 1 : i32
      %830 = arith.addi %828, %829 : i32
      llvm.store %830, %710 : i32, !llvm.ptr
      cf.br ^bb48
    ^bb50:
    %832 = arith.constant 8 : i32
    %834 = arith.extsi %832 : i32 to i64
    %833 = arith.muli %634, %834 : i64
    %831 = func.call @malloc(%833) : (i64) -> !llvm.ptr
    func.call @crt_reduce(%831, %686, %690, %694, %634) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> ()
    func.call @free(%686) : (!llvm.ptr) -> ()
    func.call @free(%690) : (!llvm.ptr) -> ()
    func.call @free(%694) : (!llvm.ptr) -> ()
    func.return %831 : !llvm.ptr
  }
  func.func @convolution_square_mod(%arg0: !llvm.ptr, %arg1: i64) -> !llvm.ptr {
    %839 = arith.constant 2 : i32
    %841 = arith.extsi %839 : i32 to i64
    %840 = arith.muli %841, %arg1 : i64
    %842 = arith.constant 1 : i32
    %844 = arith.extsi %842 : i32 to i64
    %843 = arith.subi %840, %844 : i64
    %845 = llvm.mlir.addressof @g_n : !llvm.ptr
    %846 = llvm.load %845 : !llvm.ptr -> i64
    %848 = llvm.mlir.addressof @P1 : !llvm.ptr
    %849 = llvm.load %848 : !llvm.ptr -> i64
    %850 = llvm.mlir.addressof @P2 : !llvm.ptr
    %851 = llvm.load %850 : !llvm.ptr -> i64
    %852 = llvm.mlir.addressof @P3 : !llvm.ptr
    %853 = llvm.load %852 : !llvm.ptr -> i64
    %854 = llvm.mlir.constant(1 : i64) : i64
    %855 = llvm.alloca %854 x !llvm.array<3 x i64> : (i64) -> !llvm.ptr
    %856 = llvm.mlir.zero : !llvm.array<3 x i64>
    llvm.store %856, %855 : !llvm.array<3 x i64>, !llvm.ptr
    %857 = llvm.mlir.constant(0 : i64) : i64
    %858 = llvm.getelementptr %855[0, %857] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %849, %858 : i64, !llvm.ptr
    %859 = llvm.mlir.constant(1 : i64) : i64
    %860 = llvm.getelementptr %855[0, %859] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %851, %860 : i64, !llvm.ptr
    %861 = llvm.mlir.constant(2 : i64) : i64
    %862 = llvm.getelementptr %855[0, %861] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
    llvm.store %853, %862 : i64, !llvm.ptr
    %864 = llvm.mlir.addressof @g_roots0 : !llvm.ptr
    %865 = llvm.load %864 : !llvm.ptr -> !llvm.ptr
    %866 = llvm.mlir.addressof @g_roots1 : !llvm.ptr
    %867 = llvm.load %866 : !llvm.ptr -> !llvm.ptr
    %868 = llvm.mlir.addressof @g_roots2 : !llvm.ptr
    %869 = llvm.load %868 : !llvm.ptr -> !llvm.ptr
    %870 = llvm.mlir.constant(1 : i64) : i64
    %871 = llvm.alloca %870 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %872 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %872, %871 : !llvm.array<3 x ptr>, !llvm.ptr
    %873 = llvm.mlir.constant(0 : i64) : i64
    %874 = llvm.getelementptr %871[0, %873] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %865, %874 : !llvm.ptr, !llvm.ptr
    %875 = llvm.mlir.constant(1 : i64) : i64
    %876 = llvm.getelementptr %871[0, %875] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %867, %876 : !llvm.ptr, !llvm.ptr
    %877 = llvm.mlir.constant(2 : i64) : i64
    %878 = llvm.getelementptr %871[0, %877] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %869, %878 : !llvm.ptr, !llvm.ptr
    %880 = llvm.mlir.addressof @g_roots_inv0 : !llvm.ptr
    %881 = llvm.load %880 : !llvm.ptr -> !llvm.ptr
    %882 = llvm.mlir.addressof @g_roots_inv1 : !llvm.ptr
    %883 = llvm.load %882 : !llvm.ptr -> !llvm.ptr
    %884 = llvm.mlir.addressof @g_roots_inv2 : !llvm.ptr
    %885 = llvm.load %884 : !llvm.ptr -> !llvm.ptr
    %886 = llvm.mlir.constant(1 : i64) : i64
    %887 = llvm.alloca %886 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %888 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %888, %887 : !llvm.array<3 x ptr>, !llvm.ptr
    %889 = llvm.mlir.constant(0 : i64) : i64
    %890 = llvm.getelementptr %887[0, %889] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %881, %890 : !llvm.ptr, !llvm.ptr
    %891 = llvm.mlir.constant(1 : i64) : i64
    %892 = llvm.getelementptr %887[0, %891] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %883, %892 : !llvm.ptr, !llvm.ptr
    %893 = llvm.mlir.constant(2 : i64) : i64
    %894 = llvm.getelementptr %887[0, %893] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %885, %894 : !llvm.ptr, !llvm.ptr
    %896 = arith.constant 8 : i32
    %898 = arith.extsi %896 : i32 to i64
    %897 = arith.muli %843, %898 : i64
    %895 = func.call @malloc(%897) : (i64) -> !llvm.ptr
    %900 = arith.constant 8 : i32
    %902 = arith.extsi %900 : i32 to i64
    %901 = arith.muli %843, %902 : i64
    %899 = func.call @malloc(%901) : (i64) -> !llvm.ptr
    %904 = arith.constant 8 : i32
    %906 = arith.extsi %904 : i32 to i64
    %905 = arith.muli %843, %906 : i64
    %903 = func.call @malloc(%905) : (i64) -> !llvm.ptr
    %908 = llvm.mlir.constant(1 : i64) : i64
    %909 = llvm.alloca %908 x !llvm.array<3 x ptr> : (i64) -> !llvm.ptr
    %910 = llvm.mlir.zero : !llvm.array<3 x ptr>
    llvm.store %910, %909 : !llvm.array<3 x ptr>, !llvm.ptr
    %911 = llvm.mlir.constant(0 : i64) : i64
    %912 = llvm.getelementptr %909[0, %911] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %895, %912 : !llvm.ptr, !llvm.ptr
    %913 = llvm.mlir.constant(1 : i64) : i64
    %914 = llvm.getelementptr %909[0, %913] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %899, %914 : !llvm.ptr, !llvm.ptr
    %915 = llvm.mlir.constant(2 : i64) : i64
    %916 = llvm.getelementptr %909[0, %915] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
    llvm.store %903, %916 : !llvm.ptr, !llvm.ptr
    %917 = arith.constant 0 : i32
    %918 = llvm.mlir.constant(1 : i64) : i64
    %919 = llvm.alloca %918 x i32 : (i64) -> !llvm.ptr
    llvm.store %917, %919 : i32, !llvm.ptr
    cf.br ^bb60
    ^bb60:
    %920 = llvm.load %919 : !llvm.ptr -> i32
    %921 = arith.constant 3 : i32
    %922 = arith.cmpi slt, %920, %921 : i32
    cf.cond_br %922, ^bb61, ^bb62
    ^bb61:
      %924 = llvm.load %919 : !llvm.ptr -> i32
      %925 = arith.extsi %924 : i32 to i64
      %926 = llvm.getelementptr %855[0, %925] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x i64>
      %923 = llvm.load %926 : !llvm.ptr -> i64
      %928 = arith.constant 8 : i32
      %929 = arith.extsi %928 : i32 to i64
      %927 = func.call @calloc(%846, %929) : (i64, i64) -> !llvm.ptr
      %930 = arith.constant 0 : i32
      %931 = arith.extsi %930 : i32 to i64
      %932 = llvm.mlir.constant(1 : i64) : i64
      %933 = llvm.alloca %932 x i64 : (i64) -> !llvm.ptr
      llvm.store %931, %933 : i64, !llvm.ptr
      cf.br ^bb63
      ^bb63:
      %934 = llvm.load %933 : !llvm.ptr -> i64
      %935 = arith.cmpi slt, %934, %arg1 : i64
      cf.cond_br %935, ^bb64, ^bb65
      ^bb64:
        %937 = llvm.load %933 : !llvm.ptr -> i64
        %938 = llvm.getelementptr %arg0[%937] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %936 = llvm.load %938 : !llvm.ptr -> i64
        %939 = arith.remsi %936, %923 : i64
        %940 = arith.addi %939, %923 : i64
        %941 = arith.remsi %940, %923 : i64
        %942 = llvm.load %933 : !llvm.ptr -> i64
        %943 = llvm.getelementptr %927[%942] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %941, %943 : i64, !llvm.ptr
        %944 = llvm.load %933 : !llvm.ptr -> i64
        %945 = arith.constant 1 : i32
        %947 = arith.extsi %945 : i32 to i64
        %946 = arith.addi %944, %947 : i64
        llvm.store %946, %933 : i64, !llvm.ptr
        cf.br ^bb63
      ^bb65:
      %950 = llvm.load %919 : !llvm.ptr -> i32
      %951 = arith.extsi %950 : i32 to i64
      %952 = llvm.getelementptr %871[0, %951] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %949 = llvm.load %952 : !llvm.ptr -> !llvm.ptr
      %954 = llvm.load %919 : !llvm.ptr -> i32
      %955 = arith.extsi %954 : i32 to i64
      %956 = llvm.getelementptr %887[0, %955] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %953 = llvm.load %956 : !llvm.ptr -> !llvm.ptr
      %957 = llvm.mlir.addressof @g_rev : !llvm.ptr
      %958 = llvm.load %957 : !llvm.ptr -> !llvm.ptr
      %959 = arith.constant 0 : i32
      func.call @ntt(%927, %846, %923, %949, %953, %958, %959) : (!llvm.ptr, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      %960 = arith.constant 0 : i32
      %961 = arith.extsi %960 : i32 to i64
      llvm.store %961, %933 : i64, !llvm.ptr
      cf.br ^bb66
      ^bb66:
      %962 = llvm.load %933 : !llvm.ptr -> i64
      %963 = arith.cmpi slt, %962, %846 : i64
      cf.cond_br %963, ^bb67, ^bb68
      ^bb67:
        %965 = llvm.load %933 : !llvm.ptr -> i64
        %966 = llvm.getelementptr %927[%965] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %964 = llvm.load %966 : !llvm.ptr -> i64
        %967 = arith.extsi %964 : i64 to i128
        %969 = llvm.load %933 : !llvm.ptr -> i64
        %970 = llvm.getelementptr %927[%969] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %968 = llvm.load %970 : !llvm.ptr -> i64
        %971 = arith.extsi %968 : i64 to i128
        %973 = arith.trunci %967 : i128 to i64
        %974 = arith.trunci %971 : i128 to i64
        %972 = arith.muli %973, %974 : i64
        %975 = arith.extsi %923 : i64 to i128
        %977 = arith.trunci %975 : i128 to i64
        %976 = arith.remsi %972, %977 : i64
        %978 = llvm.load %933 : !llvm.ptr -> i64
        %979 = llvm.getelementptr %927[%978] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %976, %979 : i64, !llvm.ptr
        %980 = llvm.load %933 : !llvm.ptr -> i64
        %981 = arith.constant 1 : i32
        %983 = arith.extsi %981 : i32 to i64
        %982 = arith.addi %980, %983 : i64
        llvm.store %982, %933 : i64, !llvm.ptr
        cf.br ^bb66
      ^bb68:
      %986 = llvm.load %919 : !llvm.ptr -> i32
      %987 = arith.extsi %986 : i32 to i64
      %988 = llvm.getelementptr %871[0, %987] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %985 = llvm.load %988 : !llvm.ptr -> !llvm.ptr
      %990 = llvm.load %919 : !llvm.ptr -> i32
      %991 = arith.extsi %990 : i32 to i64
      %992 = llvm.getelementptr %887[0, %991] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %989 = llvm.load %992 : !llvm.ptr -> !llvm.ptr
      %993 = llvm.mlir.addressof @g_rev : !llvm.ptr
      %994 = llvm.load %993 : !llvm.ptr -> !llvm.ptr
      %995 = arith.constant 1 : i32
      func.call @ntt(%927, %846, %923, %985, %989, %994, %995) : (!llvm.ptr, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      %998 = llvm.load %919 : !llvm.ptr -> i32
      %999 = arith.extsi %998 : i32 to i64
      %1000 = llvm.getelementptr %909[0, %999] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.array<3 x ptr>
      %997 = llvm.load %1000 : !llvm.ptr -> !llvm.ptr
      %1001 = arith.constant 8 : i32
      %1003 = arith.extsi %1001 : i32 to i64
      %1002 = arith.muli %843, %1003 : i64
      %996 = func.call @memcpy(%997, %927, %1002) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
      func.call @free(%927) : (!llvm.ptr) -> ()
      %1005 = llvm.load %919 : !llvm.ptr -> i32
      %1006 = arith.constant 1 : i32
      %1007 = arith.addi %1005, %1006 : i32
      llvm.store %1007, %919 : i32, !llvm.ptr
      cf.br ^bb60
    ^bb62:
    %1009 = arith.constant 8 : i32
    %1011 = arith.extsi %1009 : i32 to i64
    %1010 = arith.muli %843, %1011 : i64
    %1008 = func.call @malloc(%1010) : (i64) -> !llvm.ptr
    func.call @crt_reduce(%1008, %895, %899, %903, %843) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> ()
    func.call @free(%895) : (!llvm.ptr) -> ()
    func.call @free(%899) : (!llvm.ptr) -> ()
    func.call @free(%903) : (!llvm.ptr) -> ()
    func.return %1008 : !llvm.ptr
  }
  func.func @pow16_mod(%arg0: i64) -> i64 {
    %1016 = arith.extsi %arg0 : i64 to i128
    %1017 = arith.extsi %arg0 : i64 to i128
    %1019 = arith.trunci %1016 : i128 to i64
    %1020 = arith.trunci %1017 : i128 to i64
    %1018 = arith.muli %1019, %1020 : i64
    %1021 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1022 = llvm.load %1021 : !llvm.ptr -> i64
    %1023 = arith.extsi %1022 : i64 to i128
    %1025 = arith.trunci %1023 : i128 to i64
    %1024 = arith.remsi %1018, %1025 : i64
    %1026 = arith.extsi %1024 : i64 to i128
    %1027 = arith.extsi %1024 : i64 to i128
    %1029 = arith.trunci %1026 : i128 to i64
    %1030 = arith.trunci %1027 : i128 to i64
    %1028 = arith.muli %1029, %1030 : i64
    %1031 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1032 = llvm.load %1031 : !llvm.ptr -> i64
    %1033 = arith.extsi %1032 : i64 to i128
    %1035 = arith.trunci %1033 : i128 to i64
    %1034 = arith.remsi %1028, %1035 : i64
    %1036 = arith.extsi %1034 : i64 to i128
    %1037 = arith.extsi %1034 : i64 to i128
    %1039 = arith.trunci %1036 : i128 to i64
    %1040 = arith.trunci %1037 : i128 to i64
    %1038 = arith.muli %1039, %1040 : i64
    %1041 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1042 = llvm.load %1041 : !llvm.ptr -> i64
    %1043 = arith.extsi %1042 : i64 to i128
    %1045 = arith.trunci %1043 : i128 to i64
    %1044 = arith.remsi %1038, %1045 : i64
    %1046 = arith.extsi %1044 : i64 to i128
    %1047 = arith.extsi %1044 : i64 to i128
    %1049 = arith.trunci %1046 : i128 to i64
    %1050 = arith.trunci %1047 : i128 to i64
    %1048 = arith.muli %1049, %1050 : i64
    %1051 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1052 = llvm.load %1051 : !llvm.ptr -> i64
    %1053 = arith.extsi %1052 : i64 to i128
    %1055 = arith.trunci %1053 : i128 to i64
    %1054 = arith.remsi %1048, %1055 : i64
    func.return %1054 : i64
  }
  func.func @main() -> i32 {
    %1056 = arith.constant 100000 : i32
    %1057 = arith.extsi %1056 : i32 to i64
    %1058 = arith.constant 9999995705032704 : i32
    %1059 = arith.extsi %1058 : i32 to i64
    %1060 = arith.divsi %1059, %1057 : i64
    %1062 = arith.constant 2 : i32
    %1063 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1064 = llvm.load %1063 : !llvm.ptr -> i64
    %1065 = arith.constant 1 : i32
    %1067 = arith.extsi %1065 : i32 to i64
    %1066 = arith.subi %1064, %1067 : i64
    %1068 = arith.remsi %1060, %1066 : i64
    %1069 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1070 = llvm.load %1069 : !llvm.ptr -> i64
    %1071 = arith.extsi %1062 : i32 to i64
    %1061 = func.call @mod_pow(%1071, %1068, %1070) : (i64, i64, i64) -> i64
    %1073 = arith.constant 1 : i32
    %1075 = arith.extsi %1073 : i32 to i64
    %1074 = arith.addi %1057, %1075 : i64
    %1076 = arith.constant 8 : i32
    %1078 = arith.extsi %1076 : i32 to i64
    %1077 = arith.muli %1074, %1078 : i64
    %1072 = func.call @malloc(%1077) : (i64) -> !llvm.ptr
    %1080 = arith.constant 1 : i32
    %1082 = arith.extsi %1080 : i32 to i64
    %1081 = arith.addi %1057, %1082 : i64
    %1083 = arith.constant 8 : i32
    %1085 = arith.extsi %1083 : i32 to i64
    %1084 = arith.muli %1081, %1085 : i64
    %1079 = func.call @malloc(%1084) : (i64) -> !llvm.ptr
    %1086 = arith.constant 1 : i32
    %1087 = arith.constant 0 : i32
    %1088 = arith.extsi %1086 : i32 to i64
    %1089 = arith.extsi %1087 : i32 to i64
    %1090 = llvm.getelementptr %1072[%1089] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %1088, %1090 : i64, !llvm.ptr
    %1091 = arith.constant 1 : i32
    %1092 = arith.extsi %1091 : i32 to i64
    %1093 = llvm.mlir.constant(1 : i64) : i64
    %1094 = llvm.alloca %1093 x i64 : (i64) -> !llvm.ptr
    llvm.store %1092, %1094 : i64, !llvm.ptr
    cf.br ^bb69
    ^bb69:
    %1095 = llvm.load %1094 : !llvm.ptr -> i64
    %1096 = arith.cmpi sle, %1095, %1057 : i64
    cf.cond_br %1096, ^bb70, ^bb71
    ^bb70:
      %1098 = llvm.load %1094 : !llvm.ptr -> i64
      %1099 = arith.constant 1 : i32
      %1101 = arith.extsi %1099 : i32 to i64
      %1100 = arith.subi %1098, %1101 : i64
      %1102 = llvm.getelementptr %1072[%1100] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1097 = llvm.load %1102 : !llvm.ptr -> i64
      %1103 = arith.extsi %1097 : i64 to i128
      %1104 = llvm.load %1094 : !llvm.ptr -> i64
      %1105 = arith.extsi %1104 : i64 to i128
      %1107 = arith.trunci %1103 : i128 to i64
      %1108 = arith.trunci %1105 : i128 to i64
      %1106 = arith.muli %1107, %1108 : i64
      %1109 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1110 = llvm.load %1109 : !llvm.ptr -> i64
      %1111 = arith.extsi %1110 : i64 to i128
      %1113 = arith.trunci %1111 : i128 to i64
      %1112 = arith.remsi %1106, %1113 : i64
      %1114 = llvm.load %1094 : !llvm.ptr -> i64
      %1115 = llvm.getelementptr %1072[%1114] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1112, %1115 : i64, !llvm.ptr
      %1116 = llvm.load %1094 : !llvm.ptr -> i64
      %1117 = arith.constant 1 : i32
      %1119 = arith.extsi %1117 : i32 to i64
      %1118 = arith.addi %1116, %1119 : i64
      llvm.store %1118, %1094 : i64, !llvm.ptr
      cf.br ^bb69
    ^bb71:
    %1122 = llvm.getelementptr %1072[%1057] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %1121 = llvm.load %1122 : !llvm.ptr -> i64
    %1123 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1124 = llvm.load %1123 : !llvm.ptr -> i64
    %1125 = arith.constant 2 : i32
    %1127 = arith.extsi %1125 : i32 to i64
    %1126 = arith.subi %1124, %1127 : i64
    %1128 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1129 = llvm.load %1128 : !llvm.ptr -> i64
    %1120 = func.call @mod_pow(%1121, %1126, %1129) : (i64, i64, i64) -> i64
    %1130 = llvm.getelementptr %1079[%1057] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %1120, %1130 : i64, !llvm.ptr
    llvm.store %1057, %1094 : i64, !llvm.ptr
    cf.br ^bb72
    ^bb72:
    %1131 = llvm.load %1094 : !llvm.ptr -> i64
    %1132 = arith.constant 1 : i32
    %1134 = arith.extsi %1132 : i32 to i64
    %1133 = arith.cmpi sge, %1131, %1134 : i64
    cf.cond_br %1133, ^bb73, ^bb74
    ^bb73:
      %1136 = llvm.load %1094 : !llvm.ptr -> i64
      %1137 = llvm.getelementptr %1079[%1136] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1135 = llvm.load %1137 : !llvm.ptr -> i64
      %1138 = arith.extsi %1135 : i64 to i128
      %1139 = llvm.load %1094 : !llvm.ptr -> i64
      %1140 = arith.extsi %1139 : i64 to i128
      %1142 = arith.trunci %1138 : i128 to i64
      %1143 = arith.trunci %1140 : i128 to i64
      %1141 = arith.muli %1142, %1143 : i64
      %1144 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1145 = llvm.load %1144 : !llvm.ptr -> i64
      %1146 = arith.extsi %1145 : i64 to i128
      %1148 = arith.trunci %1146 : i128 to i64
      %1147 = arith.remsi %1141, %1148 : i64
      %1149 = llvm.load %1094 : !llvm.ptr -> i64
      %1150 = arith.constant 1 : i32
      %1152 = arith.extsi %1150 : i32 to i64
      %1151 = arith.subi %1149, %1152 : i64
      %1153 = llvm.getelementptr %1079[%1151] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1147, %1153 : i64, !llvm.ptr
      %1154 = llvm.load %1094 : !llvm.ptr -> i64
      %1155 = arith.constant 1 : i32
      %1157 = arith.extsi %1155 : i32 to i64
      %1156 = arith.subi %1154, %1157 : i64
      llvm.store %1156, %1094 : i64, !llvm.ptr
      cf.br ^bb72
    ^bb74:
    %1159 = arith.constant 1 : i32
    %1161 = arith.extsi %1159 : i32 to i64
    %1160 = arith.addi %1057, %1161 : i64
    %1162 = arith.constant 8 : i32
    %1164 = arith.extsi %1162 : i32 to i64
    %1163 = arith.muli %1160, %1164 : i64
    %1158 = func.call @malloc(%1163) : (i64) -> !llvm.ptr
    %1166 = arith.constant 1 : i32
    %1168 = arith.extsi %1166 : i32 to i64
    %1167 = arith.addi %1057, %1168 : i64
    %1169 = arith.constant 8 : i32
    %1171 = arith.extsi %1169 : i32 to i64
    %1170 = arith.muli %1167, %1171 : i64
    %1165 = func.call @malloc(%1170) : (i64) -> !llvm.ptr
    %1172 = arith.constant 0 : i32
    %1173 = arith.extsi %1172 : i32 to i64
    llvm.store %1173, %1094 : i64, !llvm.ptr
    cf.br ^bb75
    ^bb75:
    %1174 = llvm.load %1094 : !llvm.ptr -> i64
    %1175 = arith.cmpi sle, %1174, %1057 : i64
    cf.cond_br %1175, ^bb76, ^bb77
    ^bb76:
      %1178 = llvm.load %1094 : !llvm.ptr -> i64
      %1179 = llvm.getelementptr %1072[%1178] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1177 = llvm.load %1179 : !llvm.ptr -> i64
      %1176 = func.call @pow16_mod(%1177) : (i64) -> i64
      %1180 = llvm.load %1094 : !llvm.ptr -> i64
      %1181 = llvm.getelementptr %1158[%1180] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1176, %1181 : i64, !llvm.ptr
      %1184 = llvm.load %1094 : !llvm.ptr -> i64
      %1185 = llvm.getelementptr %1079[%1184] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1183 = llvm.load %1185 : !llvm.ptr -> i64
      %1182 = func.call @pow16_mod(%1183) : (i64) -> i64
      %1186 = llvm.load %1094 : !llvm.ptr -> i64
      %1187 = llvm.getelementptr %1165[%1186] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1182, %1187 : i64, !llvm.ptr
      %1188 = llvm.load %1094 : !llvm.ptr -> i64
      %1189 = arith.constant 1 : i32
      %1191 = arith.extsi %1189 : i32 to i64
      %1190 = arith.addi %1188, %1191 : i64
      llvm.store %1190, %1094 : i64, !llvm.ptr
      cf.br ^bb75
    ^bb77:
    %1192 = arith.constant 2 : i32
    %1193 = arith.constant 1 : i32
    %1195 = arith.extsi %1193 : i32 to i64
    %1194 = arith.addi %1057, %1195 : i64
    %1197 = arith.extsi %1192 : i32 to i64
    %1196 = arith.muli %1197, %1194 : i64
    %1198 = arith.constant 1 : i32
    %1200 = arith.extsi %1198 : i32 to i64
    %1199 = arith.subi %1196, %1200 : i64
    %1201 = func.call @ceil_pow2(%1199) : (i64) -> i64
    func.call @ctx_init(%1201) : (i64) -> ()
    %1204 = arith.constant 1 : i32
    %1206 = arith.extsi %1204 : i32 to i64
    %1205 = arith.addi %1057, %1206 : i64
    %1203 = func.call @convolution_square_mod(%1165, %1205) : (!llvm.ptr, i64) -> !llvm.ptr
    %1208 = arith.constant 1 : i32
    %1210 = arith.extsi %1208 : i32 to i64
    %1209 = arith.addi %1057, %1210 : i64
    %1211 = arith.constant 8 : i32
    %1213 = arith.extsi %1211 : i32 to i64
    %1212 = arith.muli %1209, %1213 : i64
    %1207 = func.call @malloc(%1212) : (i64) -> !llvm.ptr
    %1214 = arith.constant 0 : i32
    %1215 = arith.extsi %1214 : i32 to i64
    llvm.store %1215, %1094 : i64, !llvm.ptr
    cf.br ^bb78
    ^bb78:
    %1216 = llvm.load %1094 : !llvm.ptr -> i64
    %1217 = arith.cmpi sle, %1216, %1057 : i64
    cf.cond_br %1217, ^bb79, ^bb80
    ^bb79:
      %1219 = llvm.load %1094 : !llvm.ptr -> i64
      %1220 = llvm.getelementptr %1158[%1219] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1218 = llvm.load %1220 : !llvm.ptr -> i64
      %1221 = arith.extsi %1218 : i64 to i128
      %1223 = llvm.load %1094 : !llvm.ptr -> i64
      %1224 = llvm.getelementptr %1203[%1223] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1222 = llvm.load %1224 : !llvm.ptr -> i64
      %1225 = arith.extsi %1222 : i64 to i128
      %1227 = arith.trunci %1221 : i128 to i64
      %1228 = arith.trunci %1225 : i128 to i64
      %1226 = arith.muli %1227, %1228 : i64
      %1229 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1230 = llvm.load %1229 : !llvm.ptr -> i64
      %1231 = arith.extsi %1230 : i64 to i128
      %1233 = arith.trunci %1231 : i128 to i64
      %1232 = arith.remsi %1226, %1233 : i64
      %1234 = llvm.load %1094 : !llvm.ptr -> i64
      %1235 = llvm.getelementptr %1207[%1234] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1232, %1235 : i64, !llvm.ptr
      %1236 = llvm.load %1094 : !llvm.ptr -> i64
      %1237 = arith.constant 1 : i32
      %1239 = arith.extsi %1237 : i32 to i64
      %1238 = arith.addi %1236, %1239 : i64
      llvm.store %1238, %1094 : i64, !llvm.ptr
      cf.br ^bb78
    ^bb80:
    func.call @free(%1203) : (!llvm.ptr) -> ()
    %1242 = arith.constant 1 : i32
    %1244 = arith.extsi %1242 : i32 to i64
    %1243 = arith.addi %1057, %1244 : i64
    %1245 = arith.constant 8 : i32
    %1247 = arith.extsi %1245 : i32 to i64
    %1246 = arith.muli %1243, %1247 : i64
    %1241 = func.call @malloc(%1246) : (i64) -> !llvm.ptr
    %1248 = arith.constant 0 : i32
    %1249 = arith.extsi %1248 : i32 to i64
    llvm.store %1249, %1094 : i64, !llvm.ptr
    cf.br ^bb81
    ^bb81:
    %1250 = llvm.load %1094 : !llvm.ptr -> i64
    %1251 = arith.cmpi sle, %1250, %1057 : i64
    cf.cond_br %1251, ^bb82, ^bb83
    ^bb82:
      %1253 = llvm.load %1094 : !llvm.ptr -> i64
      %1254 = llvm.getelementptr %1207[%1253] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1252 = llvm.load %1254 : !llvm.ptr -> i64
      %1255 = arith.extsi %1252 : i64 to i128
      %1257 = llvm.load %1094 : !llvm.ptr -> i64
      %1258 = llvm.getelementptr %1079[%1257] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1256 = llvm.load %1258 : !llvm.ptr -> i64
      %1259 = arith.extsi %1256 : i64 to i128
      %1261 = arith.trunci %1255 : i128 to i64
      %1262 = arith.trunci %1259 : i128 to i64
      %1260 = arith.muli %1261, %1262 : i64
      %1263 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1264 = llvm.load %1263 : !llvm.ptr -> i64
      %1265 = arith.extsi %1264 : i64 to i128
      %1267 = arith.trunci %1265 : i128 to i64
      %1266 = arith.remsi %1260, %1267 : i64
      %1268 = llvm.load %1094 : !llvm.ptr -> i64
      %1269 = llvm.getelementptr %1241[%1268] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1266, %1269 : i64, !llvm.ptr
      %1270 = llvm.load %1094 : !llvm.ptr -> i64
      %1271 = arith.constant 1 : i32
      %1273 = arith.extsi %1271 : i32 to i64
      %1272 = arith.addi %1270, %1273 : i64
      llvm.store %1272, %1094 : i64, !llvm.ptr
      cf.br ^bb81
    ^bb83:
    %1274 = llvm.mlir.addressof @MOD : !llvm.ptr
    %1275 = llvm.load %1274 : !llvm.ptr -> i64
    %1276 = arith.constant 2 : i32
    %1278 = arith.extsi %1276 : i32 to i64
    %1277 = arith.subi %1275, %1278 : i64
    %1280 = arith.constant 1 : i32
    %1282 = arith.extsi %1280 : i32 to i64
    %1281 = arith.addi %1057, %1282 : i64
    %1283 = arith.constant 8 : i32
    %1285 = arith.extsi %1283 : i32 to i64
    %1284 = arith.muli %1281, %1285 : i64
    %1279 = func.call @malloc(%1284) : (i64) -> !llvm.ptr
    %1286 = arith.constant 1 : i32
    %1287 = arith.extsi %1286 : i32 to i64
    %1288 = llvm.mlir.constant(1 : i64) : i64
    %1289 = llvm.alloca %1288 x i64 : (i64) -> !llvm.ptr
    llvm.store %1287, %1289 : i64, !llvm.ptr
    %1290 = arith.constant 0 : i32
    %1291 = arith.extsi %1290 : i32 to i64
    llvm.store %1291, %1094 : i64, !llvm.ptr
    cf.br ^bb84
    ^bb84:
    %1292 = llvm.load %1094 : !llvm.ptr -> i64
    %1293 = arith.cmpi sle, %1292, %1057 : i64
    cf.cond_br %1293, ^bb85, ^bb86
    ^bb85:
      %1294 = llvm.load %1289 : !llvm.ptr -> i64
      %1295 = arith.extsi %1294 : i64 to i128
      %1297 = llvm.load %1094 : !llvm.ptr -> i64
      %1298 = llvm.getelementptr %1079[%1297] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1296 = llvm.load %1298 : !llvm.ptr -> i64
      %1299 = arith.extsi %1296 : i64 to i128
      %1301 = arith.trunci %1295 : i128 to i64
      %1302 = arith.trunci %1299 : i128 to i64
      %1300 = arith.muli %1301, %1302 : i64
      %1303 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1304 = llvm.load %1303 : !llvm.ptr -> i64
      %1305 = arith.extsi %1304 : i64 to i128
      %1307 = arith.trunci %1305 : i128 to i64
      %1306 = arith.remsi %1300, %1307 : i64
      %1308 = llvm.load %1094 : !llvm.ptr -> i64
      %1309 = llvm.getelementptr %1279[%1308] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1306, %1309 : i64, !llvm.ptr
      %1310 = llvm.load %1289 : !llvm.ptr -> i64
      %1311 = arith.extsi %1310 : i64 to i128
      %1312 = arith.extsi %1277 : i64 to i128
      %1314 = arith.trunci %1311 : i128 to i64
      %1315 = arith.trunci %1312 : i128 to i64
      %1313 = arith.muli %1314, %1315 : i64
      %1316 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1317 = llvm.load %1316 : !llvm.ptr -> i64
      %1318 = arith.extsi %1317 : i64 to i128
      %1320 = arith.trunci %1318 : i128 to i64
      %1319 = arith.remsi %1313, %1320 : i64
      llvm.store %1319, %1289 : i64, !llvm.ptr
      %1321 = llvm.load %1094 : !llvm.ptr -> i64
      %1322 = arith.constant 1 : i32
      %1324 = arith.extsi %1322 : i32 to i64
      %1323 = arith.addi %1321, %1324 : i64
      llvm.store %1323, %1094 : i64, !llvm.ptr
      cf.br ^bb84
    ^bb86:
    %1326 = arith.constant 1 : i32
    %1328 = arith.extsi %1326 : i32 to i64
    %1327 = arith.addi %1057, %1328 : i64
    %1329 = arith.constant 1 : i32
    %1331 = arith.extsi %1329 : i32 to i64
    %1330 = arith.addi %1057, %1331 : i64
    %1325 = func.call @convolution_mod(%1241, %1327, %1279, %1330) : (!llvm.ptr, i64, !llvm.ptr, i64) -> !llvm.ptr
    %1333 = arith.constant 1 : i32
    %1335 = arith.extsi %1333 : i32 to i64
    %1334 = arith.addi %1057, %1335 : i64
    %1336 = arith.constant 8 : i32
    %1338 = arith.extsi %1336 : i32 to i64
    %1337 = arith.muli %1334, %1338 : i64
    %1332 = func.call @malloc(%1337) : (i64) -> !llvm.ptr
    %1339 = arith.constant 0 : i32
    %1340 = arith.extsi %1339 : i32 to i64
    llvm.store %1340, %1094 : i64, !llvm.ptr
    cf.br ^bb87
    ^bb87:
    %1341 = llvm.load %1094 : !llvm.ptr -> i64
    %1342 = arith.cmpi sle, %1341, %1057 : i64
    cf.cond_br %1342, ^bb88, ^bb89
    ^bb88:
      %1344 = llvm.load %1094 : !llvm.ptr -> i64
      %1345 = llvm.getelementptr %1325[%1344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1343 = llvm.load %1345 : !llvm.ptr -> i64
      %1346 = arith.extsi %1343 : i64 to i128
      %1348 = llvm.load %1094 : !llvm.ptr -> i64
      %1349 = llvm.getelementptr %1072[%1348] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1347 = llvm.load %1349 : !llvm.ptr -> i64
      %1350 = arith.extsi %1347 : i64 to i128
      %1352 = arith.trunci %1346 : i128 to i64
      %1353 = arith.trunci %1350 : i128 to i64
      %1351 = arith.muli %1352, %1353 : i64
      %1354 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1355 = llvm.load %1354 : !llvm.ptr -> i64
      %1356 = arith.extsi %1355 : i64 to i128
      %1358 = arith.trunci %1356 : i128 to i64
      %1357 = arith.remsi %1351, %1358 : i64
      %1359 = llvm.load %1094 : !llvm.ptr -> i64
      %1360 = llvm.getelementptr %1332[%1359] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1357, %1360 : i64, !llvm.ptr
      %1361 = llvm.load %1094 : !llvm.ptr -> i64
      %1362 = arith.constant 1 : i32
      %1364 = arith.extsi %1362 : i32 to i64
      %1363 = arith.addi %1361, %1364 : i64
      llvm.store %1363, %1094 : i64, !llvm.ptr
      cf.br ^bb87
    ^bb89:
    func.call @free(%1325) : (!llvm.ptr) -> ()
    %1367 = arith.constant 1 : i32
    %1369 = arith.extsi %1367 : i32 to i64
    %1368 = arith.addi %1057, %1369 : i64
    %1370 = arith.constant 8 : i32
    %1372 = arith.extsi %1370 : i32 to i64
    %1371 = arith.muli %1368, %1372 : i64
    %1366 = func.call @malloc(%1371) : (i64) -> !llvm.ptr
    %1373 = arith.constant 1 : i32
    %1374 = arith.constant 0 : i32
    %1375 = arith.extsi %1373 : i32 to i64
    %1376 = arith.extsi %1374 : i32 to i64
    %1377 = llvm.getelementptr %1366[%1376] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %1375, %1377 : i64, !llvm.ptr
    %1378 = arith.constant 1 : i32
    %1379 = arith.extsi %1378 : i32 to i64
    llvm.store %1379, %1094 : i64, !llvm.ptr
    cf.br ^bb90
    ^bb90:
    %1380 = llvm.load %1094 : !llvm.ptr -> i64
    %1381 = arith.cmpi sle, %1380, %1057 : i64
    cf.cond_br %1381, ^bb91, ^bb92
    ^bb91:
      %1383 = llvm.load %1094 : !llvm.ptr -> i64
      %1384 = arith.constant 1 : i32
      %1386 = arith.extsi %1384 : i32 to i64
      %1385 = arith.subi %1383, %1386 : i64
      %1387 = llvm.getelementptr %1366[%1385] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1382 = llvm.load %1387 : !llvm.ptr -> i64
      %1388 = arith.extsi %1382 : i64 to i128
      %1389 = arith.extsi %1061 : i64 to i128
      %1391 = arith.trunci %1388 : i128 to i64
      %1392 = arith.trunci %1389 : i128 to i64
      %1390 = arith.muli %1391, %1392 : i64
      %1393 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1394 = llvm.load %1393 : !llvm.ptr -> i64
      %1395 = arith.extsi %1394 : i64 to i128
      %1397 = arith.trunci %1395 : i128 to i64
      %1396 = arith.remsi %1390, %1397 : i64
      %1398 = llvm.load %1094 : !llvm.ptr -> i64
      %1399 = llvm.getelementptr %1366[%1398] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %1396, %1399 : i64, !llvm.ptr
      %1400 = llvm.load %1094 : !llvm.ptr -> i64
      %1401 = arith.constant 1 : i32
      %1403 = arith.extsi %1401 : i32 to i64
      %1402 = arith.addi %1400, %1403 : i64
      llvm.store %1402, %1094 : i64, !llvm.ptr
      cf.br ^bb90
    ^bb92:
    %1405 = llvm.getelementptr %1072[%1057] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %1404 = llvm.load %1405 : !llvm.ptr -> i64
    %1406 = arith.constant 0 : i32
    %1407 = arith.extsi %1406 : i32 to i64
    %1408 = llvm.mlir.constant(1 : i64) : i64
    %1409 = llvm.alloca %1408 x i64 : (i64) -> !llvm.ptr
    llvm.store %1407, %1409 : i64, !llvm.ptr
    %1410 = arith.constant 0 : i32
    %1411 = arith.extsi %1410 : i32 to i64
    llvm.store %1411, %1094 : i64, !llvm.ptr
    cf.br ^bb93
    ^bb93:
    %1412 = llvm.load %1094 : !llvm.ptr -> i64
    %1413 = arith.cmpi sle, %1412, %1057 : i64
    cf.cond_br %1413, ^bb94, ^bb95
    ^bb94:
      %1414 = arith.extsi %1404 : i64 to i128
      %1416 = llvm.load %1094 : !llvm.ptr -> i64
      %1417 = llvm.getelementptr %1079[%1416] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1415 = llvm.load %1417 : !llvm.ptr -> i64
      %1418 = arith.extsi %1415 : i64 to i128
      %1420 = arith.trunci %1414 : i128 to i64
      %1421 = arith.trunci %1418 : i128 to i64
      %1419 = arith.muli %1420, %1421 : i64
      %1422 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1423 = llvm.load %1422 : !llvm.ptr -> i64
      %1424 = arith.extsi %1423 : i64 to i128
      %1426 = arith.trunci %1424 : i128 to i64
      %1425 = arith.remsi %1419, %1426 : i64
      %1427 = arith.extsi %1425 : i64 to i128
      %1429 = llvm.load %1094 : !llvm.ptr -> i64
      %1430 = arith.subi %1057, %1429 : i64
      %1431 = llvm.getelementptr %1079[%1430] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1428 = llvm.load %1431 : !llvm.ptr -> i64
      %1432 = arith.extsi %1428 : i64 to i128
      %1434 = arith.trunci %1427 : i128 to i64
      %1435 = arith.trunci %1432 : i128 to i64
      %1433 = arith.muli %1434, %1435 : i64
      %1436 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1437 = llvm.load %1436 : !llvm.ptr -> i64
      %1438 = arith.extsi %1437 : i64 to i128
      %1440 = arith.trunci %1438 : i128 to i64
      %1439 = arith.remsi %1433, %1440 : i64
      %1441 = arith.extsi %1439 : i64 to i128
      %1443 = llvm.load %1094 : !llvm.ptr -> i64
      %1444 = llvm.getelementptr %1366[%1443] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1442 = llvm.load %1444 : !llvm.ptr -> i64
      %1445 = arith.extsi %1442 : i64 to i128
      %1447 = arith.trunci %1441 : i128 to i64
      %1448 = arith.trunci %1445 : i128 to i64
      %1446 = arith.muli %1447, %1448 : i64
      %1449 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1450 = llvm.load %1449 : !llvm.ptr -> i64
      %1451 = arith.extsi %1450 : i64 to i128
      %1453 = arith.trunci %1451 : i128 to i64
      %1452 = arith.remsi %1446, %1453 : i64
      %1454 = arith.extsi %1452 : i64 to i128
      %1456 = llvm.load %1094 : !llvm.ptr -> i64
      %1457 = arith.subi %1057, %1456 : i64
      %1458 = llvm.getelementptr %1332[%1457] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %1455 = llvm.load %1458 : !llvm.ptr -> i64
      %1459 = arith.extsi %1455 : i64 to i128
      %1461 = arith.trunci %1454 : i128 to i64
      %1462 = arith.trunci %1459 : i128 to i64
      %1460 = arith.muli %1461, %1462 : i64
      %1463 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1464 = llvm.load %1463 : !llvm.ptr -> i64
      %1465 = arith.extsi %1464 : i64 to i128
      %1467 = arith.trunci %1465 : i128 to i64
      %1466 = arith.remsi %1460, %1467 : i64
      %1468 = llvm.load %1409 : !llvm.ptr -> i64
      %1469 = arith.addi %1468, %1466 : i64
      %1470 = llvm.mlir.addressof @MOD : !llvm.ptr
      %1471 = llvm.load %1470 : !llvm.ptr -> i64
      %1472 = arith.remsi %1469, %1471 : i64
      llvm.store %1472, %1409 : i64, !llvm.ptr
      %1473 = llvm.load %1094 : !llvm.ptr -> i64
      %1474 = arith.constant 1 : i32
      %1476 = arith.extsi %1474 : i32 to i64
      %1475 = arith.addi %1473, %1476 : i64
      llvm.store %1475, %1094 : i64, !llvm.ptr
      cf.br ^bb93
    ^bb95:
    func.call @free(%1072) : (!llvm.ptr) -> ()
    func.call @free(%1079) : (!llvm.ptr) -> ()
    func.call @free(%1158) : (!llvm.ptr) -> ()
    func.call @free(%1165) : (!llvm.ptr) -> ()
    func.call @free(%1207) : (!llvm.ptr) -> ()
    func.call @free(%1241) : (!llvm.ptr) -> ()
    func.call @free(%1279) : (!llvm.ptr) -> ()
    func.call @free(%1332) : (!llvm.ptr) -> ()
    func.call @free(%1366) : (!llvm.ptr) -> ()
    func.call @ctx_free() : () -> ()
    %1487 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %1488 = llvm.load %1409 : !llvm.ptr -> i64
    %1489 = llvm.call @printf(%1487, %1488) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %1490 = arith.constant 0 : i32
    func.return %1490 : i32
  }
}