Problem 921

S(1618034) mod 398874989 Pure Flow port of native/p921.c.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 921 - Golden Recurrence
# S(1618034) mod 398874989
# Pure Flow port of native/p921.c.

const MOD: i64 = 398874989
const TARGET_M: i64 = 1618034

function powmod(a0: i64, b: i64, m: i64) -> i64 {
    let mut r: i64 = 1
    let mut a: i64 = a0 % m
    if a < 0 { a = a + m }
    while b > 0 {
        if b % 2 == 1 {
            r = (((r as i128) * (a as i128)) % (m as i128)) as i64
        }
        a = (((a as i128) * (a as i128)) % (m as i128)) as i64
        b = b / 2
    }
    return r
}

function legendre(a: i64, p: i64) -> i64 {
    return powmod(a, (p - 1) / 2, p)
}

function sqrt_mod_prime(n0: i64, p: i64) -> i64 {
    let n: i64 = n0 % p
    if n < 0 { n = n + p }
    if n == 0 { return 0 }
    if p == 2 { return n }
    if legendre(n, p) != 1 { return -1 }
    if p % 4 == 3 { return powmod(n, (p + 1) / 4, p) }
    let mut q: i64 = p - 1
    let mut s: i64 = 0
    while q % 2 == 0 {
        q = q / 2
        s = s + 1
    }
    let mut z: i64 = 2
    while legendre(z, p) != p - 1 {
        z = z + 1
    }
    let c: i64 = powmod(z, q, p)
    let mut x: i64 = powmod(n, (q + 1) / 2, p)
    let mut t: i64 = powmod(n, q, p)
    let mut m: i64 = s
    while t != 1 {
        let mut t2: i64 = t
        let mut i: i64 = 1
        while i < m {
            t2 = (((t2 as i128) * (t2 as i128)) % (p as i128)) as i64
            if t2 == 1 { break }
            i = i + 1
        }
        let b: i64 = powmod(c, 1 << (m - i - 1), p)
        x = (((x as i128) * (b as i128)) % (p as i128)) as i64
        let bb: i64 = (((b as i128) * (b as i128)) % (p as i128)) as i64
        t = (((t as i128) * (bb as i128)) % (p as i128)) as i64
        c = bb
        m = i
    }
    return x
}

function main() -> i32 {
    let p: i64 = MOD
    let exp_mod: i64 = p - 1
    let inv2: i64 = powmod(2, p - 2, p)

    let mut r: i64 = sqrt_mod_prime(5, p)
    let mut inv_r: i64 = powmod(r, p - 2, p)

    let mut phi: i64 = ((((1 + r) as i128) * (inv2 as i128)) % (p as i128)) as i64
    let mut g: i64 = (((phi as i128) * (phi as i128)) % (p as i128)) as i64
    g = (((g as i128) * (phi as i128)) % (p as i128)) as i64

    # Check orientation: F_3 should be 2
    let mut u: i64 = g
    let mut uinv: i64 = powmod(u, p - 2, p)
    let mut f3: i64 = ((((u + uinv) % p) as i128) * (inv_r as i128) % (p as i128)) as i64
    if f3 != 2 {
        r = (p - r) % p
        inv_r = powmod(r, p - 2, p)
        phi = ((((1 + r) as i128) * (inv2 as i128)) % (p as i128)) as i64
        g = (((phi as i128) * (phi as i128)) % (p as i128)) as i64
        g = (((g as i128) * (phi as i128)) % (p as i128)) as i64
        u = g
        uinv = powmod(u, p - 2, p)
    }

    let inv32: i64 = powmod(32, p - 2, p)

    # Process i=2: E_1 = E_2 = 5
    let mut e_im2: i64 = 5 % exp_mod
    let mut e_im1: i64 = 5 % exp_mod

    let mut total: i64 = 0

    # i=2
    let mut e: i64 = e_im1
    u = powmod(g, e, p)
    uinv = powmod(u, p - 2, p)
    let mut f: i64 = ((((u + uinv) % p) as i128) * (inv_r as i128) % (p as i128)) as i64
    let mut l: i64 = (u - uinv) % p
    if l < 0 { l = l + p }
    let f2: i64 = (((f as i128) * (f as i128)) % (p as i128)) as i64
    let f4: i64 = (((f2 as i128) * (f2 as i128)) % (p as i128)) as i64
    let f5: i64 = (((f4 as i128) * (f as i128)) % (p as i128)) as i64
    let l2: i64 = (((l as i128) * (l as i128)) % (p as i128)) as i64
    let l4: i64 = (((l2 as i128) * (l2 as i128)) % (p as i128)) as i64
    let l5: i64 = (((l4 as i128) * (l as i128)) % (p as i128)) as i64
    let mut term: i64 = (f5 + l5) % p
    term = (((term as i128) * (inv32 as i128)) % (p as i128)) as i64
    total = term

    # i=3..m
    let mut i: i64 = 3
    while i <= TARGET_M {
        e = (((e_im1 as i128) * (e_im2 as i128)) % (exp_mod as i128)) as i64
        e_im2 = e_im1
        e_im1 = e

        u = powmod(g, e, p)
        uinv = powmod(u, p - 2, p)

        f = ((((u + uinv) % p) as i128) * (inv_r as i128) % (p as i128)) as i64
        l = (u - uinv) % p
        if l < 0 { l = l + p }

        let f2b: i64 = (((f as i128) * (f as i128)) % (p as i128)) as i64
        let f4b: i64 = (((f2b as i128) * (f2b as i128)) % (p as i128)) as i64
        let f5b: i64 = (((f4b as i128) * (f as i128)) % (p as i128)) as i64
        let l2b: i64 = (((l as i128) * (l as i128)) % (p as i128)) as i64
        let l4b: i64 = (((l2b as i128) * (l2b as i128)) % (p as i128)) as i64
        let l5b: i64 = (((l4b as i128) * (l as i128)) % (p as i128)) as i64

        term = (f5b + l5b) % p
        term = (((term as i128) * (inv32 as i128)) % (p as i128)) as i64

        total = total + term
        if total >= p { total = total - p }
        i = i + 1
    }

    printf("%lld\n", total)
    return 0
}

Generated C

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

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

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

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

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

#include <math.h>

void* _ui_state = NULL;

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

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

int64_t powmod_i64_i64_i64(int64_t a0, int64_t b, int64_t m);
int64_t legendre_i64_i64(int64_t a, int64_t p);
int64_t sqrt_mod_prime_i64_i64(int64_t n0, int64_t p);
int32_t main(void);

static const int64_t MOD = 398874989;
static const int64_t TARGET_M = 1618034;

int64_t powmod_i64_i64_i64(int64_t a0, int64_t b, int64_t m) {
    int64_t r = 1;
    int64_t a = FLOW_CHECKED_MOD((a0), (m));
    if (a < 0) {
        a = (a + m);
    }
    while (b > 0) {
        if (FLOW_CHECKED_MOD((b), (2)) == 1) {
            r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(a)))), (((__int128)(m))))));
        }
        a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(a)))), (((__int128)(m))))));
        b = FLOW_CHECKED_DIV((b), (2));
    }
    return r;
}

int64_t legendre_i64_i64(int64_t a, int64_t p) {
    return powmod_i64_i64_i64(a, FLOW_CHECKED_DIV(((p - 1)), (2)), p);
}

int64_t sqrt_mod_prime_i64_i64(int64_t n0, int64_t p) {
    int64_t n = FLOW_CHECKED_MOD((n0), (p));
    if (n < 0) {
        n = (n + p);
    }
    if (n == 0) {
        return 0;
    }
    if (p == 2) {
        return n;
    }
    if (legendre_i64_i64(n, p) != 1) {
        return (-1);
    }
    if (FLOW_CHECKED_MOD((p), (4)) == 3) {
        return powmod_i64_i64_i64(n, FLOW_CHECKED_DIV(((p + 1)), (4)), p);
    }
    int64_t q = (p - 1);
    int64_t s = 0;
    while (FLOW_CHECKED_MOD((q), (2)) == 0) {
        q = FLOW_CHECKED_DIV((q), (2));
        s = (s + 1);
    }
    int64_t z = 2;
    while (legendre_i64_i64(z, p) != (p - 1)) {
        z = (z + 1);
    }
    int64_t c = powmod_i64_i64_i64(z, q, p);
    int64_t x = powmod_i64_i64_i64(n, FLOW_CHECKED_DIV(((q + 1)), (2)), p);
    int64_t t = powmod_i64_i64_i64(n, q, p);
    int64_t m = s;
    while (t != 1) {
        int64_t t2 = t;
        int64_t i = 1;
        while (i < m) {
            t2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(t2)) * ((__int128)(t2)))), (((__int128)(p))))));
            if (t2 == 1) {
                break;
            }
            i = (i + 1);
        }
        int64_t b = powmod_i64_i64_i64(c, FLOW_CHECKED_SHL((1), (((m - i) - 1))), p);
        x = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(x)) * ((__int128)(b)))), (((__int128)(p))))));
        int64_t bb = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(p))))));
        t = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(t)) * ((__int128)(bb)))), (((__int128)(p))))));
        c = bb;
        m = i;
    }
    return x;
}

int32_t main(void) {
    int64_t p = MOD;
    int64_t exp_mod = (p - 1);
    int64_t inv2 = powmod_i64_i64_i64(2, (p - 2), p);
    int64_t r = sqrt_mod_prime_i64_i64(5, p);
    int64_t inv_r = powmod_i64_i64_i64(r, (p - 2), p);
    int64_t phi = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)((1 + r))) * ((__int128)(inv2)))), (((__int128)(p))))));
    int64_t g = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(phi)) * ((__int128)(phi)))), (((__int128)(p))))));
    g = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g)) * ((__int128)(phi)))), (((__int128)(p))))));
    int64_t u = g;
    int64_t uinv = powmod_i64_i64_i64(u, (p - 2), p);
    int64_t f3 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD(((u + uinv)), (p)))) * ((__int128)(inv_r)))), (((__int128)(p))))));
    if (f3 != 2) {
        r = FLOW_CHECKED_MOD(((p - r)), (p));
        inv_r = powmod_i64_i64_i64(r, (p - 2), p);
        phi = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)((1 + r))) * ((__int128)(inv2)))), (((__int128)(p))))));
        g = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(phi)) * ((__int128)(phi)))), (((__int128)(p))))));
        g = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g)) * ((__int128)(phi)))), (((__int128)(p))))));
        u = g;
        uinv = powmod_i64_i64_i64(u, (p - 2), p);
    }
    int64_t inv32 = powmod_i64_i64_i64(32, (p - 2), p);
    int64_t e_im2 = FLOW_CHECKED_MOD((5), (exp_mod));
    int64_t e_im1 = FLOW_CHECKED_MOD((5), (exp_mod));
    int64_t total = 0;
    int64_t e = e_im1;
    u = powmod_i64_i64_i64(g, e, p);
    uinv = powmod_i64_i64_i64(u, (p - 2), p);
    int64_t f = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD(((u + uinv)), (p)))) * ((__int128)(inv_r)))), (((__int128)(p))))));
    int64_t l = FLOW_CHECKED_MOD(((u - uinv)), (p));
    if (l < 0) {
        l = (l + p);
    }
    int64_t f2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f)) * ((__int128)(f)))), (((__int128)(p))))));
    int64_t f4 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f2)) * ((__int128)(f2)))), (((__int128)(p))))));
    int64_t f5 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f4)) * ((__int128)(f)))), (((__int128)(p))))));
    int64_t l2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(l)) * ((__int128)(l)))), (((__int128)(p))))));
    int64_t l4 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(l2)) * ((__int128)(l2)))), (((__int128)(p))))));
    int64_t l5 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(l4)) * ((__int128)(l)))), (((__int128)(p))))));
    int64_t term = FLOW_CHECKED_MOD(((f5 + l5)), (p));
    term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(term)) * ((__int128)(inv32)))), (((__int128)(p))))));
    total = term;
    int64_t i = 3;
    while (i <= TARGET_M) {
        e = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(e_im1)) * ((__int128)(e_im2)))), (((__int128)(exp_mod))))));
        e_im2 = e_im1;
        e_im1 = e;
        u = powmod_i64_i64_i64(g, e, p);
        uinv = powmod_i64_i64_i64(u, (p - 2), p);
        f = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD(((u + uinv)), (p)))) * ((__int128)(inv_r)))), (((__int128)(p))))));
        l = FLOW_CHECKED_MOD(((u - uinv)), (p));
        if (l < 0) {
            l = (l + p);
        }
        int64_t f2b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f)) * ((__int128)(f)))), (((__int128)(p))))));
        int64_t f4b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f2b)) * ((__int128)(f2b)))), (((__int128)(p))))));
        int64_t f5b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f4b)) * ((__int128)(f)))), (((__int128)(p))))));
        int64_t l2b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(l)) * ((__int128)(l)))), (((__int128)(p))))));
        int64_t l4b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(l2b)) * ((__int128)(l2b)))), (((__int128)(p))))));
        int64_t l5b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(l4b)) * ((__int128)(l)))), (((__int128)(p))))));
        term = FLOW_CHECKED_MOD(((f5b + l5b)), (p));
        term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(term)) * ((__int128)(inv32)))), (((__int128)(p))))));
        total = (total + term);
        if (total >= p) {
            total = (total - p);
        }
        i = (i + 1);
    }
    printf("%lld\n", total);
    return 0;
}

Generated MLIR

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