Problem 427

f(7500000) mod 1000000009 for sum of longest equal runs over n-sequences.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 427
# f(7500000) mod 1000000009 for sum of longest equal runs over n-sequences.

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

function mod_pow(a0: i64, e0: i64, mod: i64) -> i64 {
    let mut a: i64 = a0 % mod
    let mut e: i64 = e0
    let mut r: i64 = 1
    while e > 0 {
        if e % 2 == 1 { r = (r * a) % mod }
        a = (a * a) % mod
        e = e / 2
    }
    return r
}

function main() -> i32 {
    let n: i64 = 7500000
    let mod: i64 = 1000000009
    let n_mod: i64 = n % mod
    let a_mod: i64 = (1 - n_mod) % mod
    if a_mod < 0 { a_mod = a_mod + mod }

    let fac: ptr<i32> = calloc(n + 1, 4)
    let ifac: ptr<i32> = calloc(n + 1, 4)
    let A: ptr<i32> = calloc(n + 1, 4)
    let B: ptr<i32> = calloc(n + 1, 4)
    if fac == null || ifac == null || A == null || B == null { return 1 }

    fac[0] = 1
    let mut i: i64 = 1
    while i <= n {
        fac[i] = (((fac[i - 1] as i64) * i) % mod) as i32
        i = i + 1
    }
    ifac[n] = mod_pow(fac[n] as i64, mod - 2, mod) as i32
    i = n
    while i > 0 {
        ifac[i - 1] = (((ifac[i] as i64) * i) % mod) as i32
        i = i - 1
    }

    let mut pow_n: i64 = 1
    let mut pow_a: i64 = 1
    i = 0
    while i <= n {
        if i > 0 {
            pow_n = (pow_n * n_mod) % mod
            pow_a = (pow_a * a_mod) % mod
        }
        A[i] = ((pow_n * (ifac[i] as i64)) % mod) as i32
        B[i] = ((pow_a * (ifac[i] as i64)) % mod) as i32
        i = i + 1
    }
    free(ifac)

    let mut sum_Ak: i64 = 0
    let mut k: i64 = 2
    while k <= n {
        let q: i64 = n / k
        let km1: i64 = k - 1
        let mut m: i64 = n
        let mut idx: i64 = n
        let mut res: i64 = 0
        let mut t: i64 = 0
        while t < q {
            let bt: i64 = B[t] as i64
            let tmp: i64 = ((fac[idx] as i64) * (A[m] as i64)) % mod
            res = res + (tmp * bt) % mod
            let tmp2: i64 = ((fac[idx - k] as i64) * (A[m - k] as i64)) % mod
            res = res - (tmp2 * bt) % mod
            m = m - k
            idx = idx - km1
            t = t + 1
        }
        let tmp3: i64 = ((fac[idx] as i64) * (A[m] as i64)) % mod
        res = res + (tmp3 * (B[q] as i64)) % mod
        sum_Ak = sum_Ak + res % mod
        if (k & 1023) == 0 {
            sum_Ak = sum_Ak % mod
        }
        k = k + 1
    }
    sum_Ak = sum_Ak % mod
    if sum_Ak < 0 { sum_Ak = sum_Ak + mod }

    let ans: i64 = (mod_pow(n_mod, n + 1, mod) - sum_Ak) % mod
    if ans < 0 { ans = ans + mod }
    printf("%lld\n", ans)

    free(B)
    free(A)
    free(fac)
    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);
int32_t main(void);



int64_t mod_pow_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod) {
    int64_t a = FLOW_CHECKED_MOD((a0), (mod));
    int64_t e = e0;
    int64_t r = 1;
    while (e > 0) {
        if (FLOW_CHECKED_MOD((e), (2)) == 1) {
            r = FLOW_CHECKED_MOD(((r * a)), (mod));
        }
        a = FLOW_CHECKED_MOD(((a * a)), (mod));
        e = FLOW_CHECKED_DIV((e), (2));
    }
    return r;
}

int32_t main(void) {
    int64_t n = 7500000;
    int64_t mod = 1000000009;
    int64_t n_mod = FLOW_CHECKED_MOD((n), (mod));
    int64_t a_mod = FLOW_CHECKED_MOD(((1 - n_mod)), (mod));
    if (a_mod < 0) {
        a_mod = (a_mod + mod);
    }
    int32_t* fac = (int32_t*)(calloc((n + 1), 4));
    int32_t* ifac = (int32_t*)(calloc((n + 1), 4));
    int32_t* A = (int32_t*)(calloc((n + 1), 4));
    int32_t* B = (int32_t*)(calloc((n + 1), 4));
    if ((((fac == NULL || ifac == NULL) || A == NULL) || B == NULL)) {
        return 1;
    }
    fac[0] = 1;
    int64_t i = 1;
    while (i <= n) {
        fac[i] = ((int32_t)(FLOW_CHECKED_MOD(((((int64_t)(fac[(i - 1)])) * i)), (mod))));
        i = (i + 1);
    }
    ifac[n] = ((int32_t)(mod_pow_i64_i64_i64(((int64_t)(fac[n])), (mod - 2), mod)));
    i = n;
    while (i > 0) {
        ifac[(i - 1)] = ((int32_t)(FLOW_CHECKED_MOD(((((int64_t)(ifac[i])) * i)), (mod))));
        i = (i - 1);
    }
    int64_t pow_n = 1;
    int64_t pow_a = 1;
    i = 0;
    while (i <= n) {
        if (i > 0) {
            pow_n = FLOW_CHECKED_MOD(((pow_n * n_mod)), (mod));
            pow_a = FLOW_CHECKED_MOD(((pow_a * a_mod)), (mod));
        }
        A[i] = ((int32_t)(FLOW_CHECKED_MOD(((pow_n * ((int64_t)(ifac[i])))), (mod))));
        B[i] = ((int32_t)(FLOW_CHECKED_MOD(((pow_a * ((int64_t)(ifac[i])))), (mod))));
        i = (i + 1);
    }
    free(ifac);
    int64_t sum_Ak = 0;
    int64_t k = 2;
    while (k <= n) {
        int64_t q = FLOW_CHECKED_DIV((n), (k));
        int64_t km1 = (k - 1);
        int64_t m = n;
        int64_t idx = n;
        int64_t res = 0;
        int64_t t = 0;
        while (t < q) {
            int64_t bt = ((int64_t)(B[t]));
            int64_t tmp = FLOW_CHECKED_MOD(((((int64_t)(fac[idx])) * ((int64_t)(A[m])))), (mod));
            res = (res + FLOW_CHECKED_MOD(((tmp * bt)), (mod)));
            int64_t tmp2 = FLOW_CHECKED_MOD(((((int64_t)(fac[(idx - k)])) * ((int64_t)(A[(m - k)])))), (mod));
            res = (res - FLOW_CHECKED_MOD(((tmp2 * bt)), (mod)));
            m = (m - k);
            idx = (idx - km1);
            t = (t + 1);
        }
        int64_t tmp3 = FLOW_CHECKED_MOD(((((int64_t)(fac[idx])) * ((int64_t)(A[m])))), (mod));
        res = (res + FLOW_CHECKED_MOD(((tmp3 * ((int64_t)(B[q])))), (mod)));
        sum_Ak = (sum_Ak + FLOW_CHECKED_MOD((res), (mod)));
        if ((k & 1023) == 0) {
            sum_Ak = FLOW_CHECKED_MOD((sum_Ak), (mod));
        }
        k = (k + 1);
    }
    sum_Ak = FLOW_CHECKED_MOD((sum_Ak), (mod));
    if (sum_Ak < 0) {
        sum_Ak = (sum_Ak + mod);
    }
    int64_t ans = FLOW_CHECKED_MOD(((mod_pow_i64_i64_i64(n_mod, (n + 1), mod) - sum_Ak)), (mod));
    if (ans < 0) {
        ans = (ans + mod);
    }
    printf("%lld\n", ans);
    free(B);
    free(A);
    free(fac);
    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 @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %0 = arith.remsi %arg0, %arg2 : i64
    %1 = llvm.mlir.constant(1 : i64) : i64
    %2 = llvm.alloca %1 x i64 : (i64) -> !llvm.ptr
    llvm.store %0, %2 : i64, !llvm.ptr
    %3 = llvm.mlir.constant(1 : i64) : i64
    %4 = llvm.alloca %3 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %4 : i64, !llvm.ptr
    %5 = arith.constant 1 : i32
    %6 = arith.extsi %5 : i32 to i64
    %7 = llvm.mlir.constant(1 : i64) : i64
    %8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
    llvm.store %6, %8 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %9 = llvm.load %4 : !llvm.ptr -> i64
    %10 = arith.constant 0 : i32
    %12 = arith.extsi %10 : i32 to i64
    %11 = arith.cmpi sgt, %9, %12 : i64
    cf.cond_br %11, ^bb1, ^bb2
    ^bb1:
      %13 = llvm.load %4 : !llvm.ptr -> i64
      %14 = arith.constant 2 : i32
      %16 = arith.extsi %14 : i32 to i64
      %15 = arith.remsi %13, %16 : i64
      %17 = arith.constant 1 : i32
      %19 = arith.extsi %17 : i32 to i64
      %18 = arith.cmpi eq, %15, %19 : i64
      cf.cond_br %18, ^bb3, ^bb4
      ^bb3:
        %20 = llvm.load %8 : !llvm.ptr -> i64
        %21 = llvm.load %2 : !llvm.ptr -> i64
        %22 = arith.muli %20, %21 : i64
        %23 = arith.remsi %22, %arg2 : i64
        llvm.store %23, %8 : i64, !llvm.ptr
        cf.br ^bb5
      ^bb4:
        cf.br ^bb5
      ^bb5:
      %24 = llvm.load %2 : !llvm.ptr -> i64
      %25 = llvm.load %2 : !llvm.ptr -> i64
      %26 = arith.muli %24, %25 : i64
      %27 = arith.remsi %26, %arg2 : i64
      llvm.store %27, %2 : i64, !llvm.ptr
      %28 = llvm.load %4 : !llvm.ptr -> i64
      %29 = arith.constant 2 : i32
      %31 = arith.extsi %29 : i32 to i64
      %30 = arith.divsi %28, %31 : i64
      llvm.store %30, %4 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %32 = llvm.load %8 : !llvm.ptr -> i64
    func.return %32 : i64
  }
  func.func @main() -> i32 {
    %33 = arith.constant 7500000 : i32
    %34 = arith.extsi %33 : i32 to i64
    %35 = arith.constant 1000000009 : i32
    %36 = arith.extsi %35 : i32 to i64
    %37 = arith.remsi %34, %36 : i64
    %38 = arith.constant 1 : i32
    %40 = arith.extsi %38 : i32 to i64
    %39 = arith.subi %40, %37 : i64
    %41 = arith.remsi %39, %36 : i64
    %42 = arith.constant 0 : i32
    %44 = arith.extsi %42 : i32 to i64
    %43 = arith.cmpi slt, %41, %44 : i64
    %45 = scf.if %43 -> (i64) {
      %46 = arith.addi %41, %36 : i64
      scf.yield %46 : i64
    } else {
      scf.yield %41 : i64
    }
    %48 = arith.constant 1 : i32
    %50 = arith.extsi %48 : i32 to i64
    %49 = arith.addi %34, %50 : i64
    %51 = arith.constant 4 : i32
    %52 = arith.extsi %51 : i32 to i64
    %47 = func.call @calloc(%49, %52) : (i64, i64) -> !llvm.ptr
    %54 = arith.constant 1 : i32
    %56 = arith.extsi %54 : i32 to i64
    %55 = arith.addi %34, %56 : i64
    %57 = arith.constant 4 : i32
    %58 = arith.extsi %57 : i32 to i64
    %53 = func.call @calloc(%55, %58) : (i64, i64) -> !llvm.ptr
    %60 = arith.constant 1 : i32
    %62 = arith.extsi %60 : i32 to i64
    %61 = arith.addi %34, %62 : i64
    %63 = arith.constant 4 : i32
    %64 = arith.extsi %63 : i32 to i64
    %59 = func.call @calloc(%61, %64) : (i64, i64) -> !llvm.ptr
    %66 = arith.constant 1 : i32
    %68 = arith.extsi %66 : i32 to i64
    %67 = arith.addi %34, %68 : i64
    %69 = arith.constant 4 : i32
    %70 = arith.extsi %69 : i32 to i64
    %65 = func.call @calloc(%67, %70) : (i64, i64) -> !llvm.ptr
    %71 = llvm.mlir.zero : !llvm.ptr
    %72 = llvm.icmp "eq" %47, %71 : !llvm.ptr
    %73 = scf.if %72 -> (i1) {
      %74 = arith.constant true
      scf.yield %74 : i1
    } else {
      %75 = llvm.mlir.zero : !llvm.ptr
      %76 = llvm.icmp "eq" %53, %75 : !llvm.ptr
      scf.yield %76 : i1
    }
    %77 = scf.if %73 -> (i1) {
      %78 = arith.constant true
      scf.yield %78 : i1
    } else {
      %79 = llvm.mlir.zero : !llvm.ptr
      %80 = llvm.icmp "eq" %59, %79 : !llvm.ptr
      scf.yield %80 : i1
    }
    %81 = scf.if %77 -> (i1) {
      %82 = arith.constant true
      scf.yield %82 : i1
    } else {
      %83 = llvm.mlir.zero : !llvm.ptr
      %84 = llvm.icmp "eq" %65, %83 : !llvm.ptr
      scf.yield %84 : i1
    }
    cf.cond_br %81, ^bb6, ^bb7
    ^bb6:
      %85 = arith.constant 1 : i32
      func.return %85 : i32
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %86 = arith.constant 1 : i32
    %87 = arith.constant 0 : i32
    %88 = arith.extsi %87 : i32 to i64
    %89 = llvm.getelementptr %47[%88] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %86, %89 : i32, !llvm.ptr
    %90 = arith.constant 1 : i32
    %91 = arith.extsi %90 : i32 to i64
    %92 = llvm.mlir.constant(1 : i64) : i64
    %93 = llvm.alloca %92 x i64 : (i64) -> !llvm.ptr
    llvm.store %91, %93 : i64, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %94 = llvm.load %93 : !llvm.ptr -> i64
    %95 = arith.cmpi sle, %94, %34 : i64
    cf.cond_br %95, ^bb10, ^bb11
    ^bb10:
      %97 = llvm.load %93 : !llvm.ptr -> i64
      %98 = arith.constant 1 : i32
      %100 = arith.extsi %98 : i32 to i64
      %99 = arith.subi %97, %100 : i64
      %101 = llvm.getelementptr %47[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %96 = llvm.load %101 : !llvm.ptr -> i32
      %102 = arith.extsi %96 : i32 to i64
      %103 = llvm.load %93 : !llvm.ptr -> i64
      %104 = arith.muli %102, %103 : i64
      %105 = arith.remsi %104, %36 : i64
      %106 = arith.trunci %105 : i64 to i32
      %107 = llvm.load %93 : !llvm.ptr -> i64
      %108 = llvm.getelementptr %47[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %106, %108 : i32, !llvm.ptr
      %109 = llvm.load %93 : !llvm.ptr -> i64
      %110 = arith.constant 1 : i32
      %112 = arith.extsi %110 : i32 to i64
      %111 = arith.addi %109, %112 : i64
      llvm.store %111, %93 : i64, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %115 = llvm.getelementptr %47[%34] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    %114 = llvm.load %115 : !llvm.ptr -> i32
    %116 = arith.extsi %114 : i32 to i64
    %117 = arith.constant 2 : i32
    %119 = arith.extsi %117 : i32 to i64
    %118 = arith.subi %36, %119 : i64
    %113 = func.call @mod_pow(%116, %118, %36) : (i64, i64, i64) -> i64
    %120 = arith.trunci %113 : i64 to i32
    %121 = llvm.getelementptr %53[%34] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %120, %121 : i32, !llvm.ptr
    llvm.store %34, %93 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %122 = llvm.load %93 : !llvm.ptr -> i64
    %123 = arith.constant 0 : i32
    %125 = arith.extsi %123 : i32 to i64
    %124 = arith.cmpi sgt, %122, %125 : i64
    cf.cond_br %124, ^bb13, ^bb14
    ^bb13:
      %127 = llvm.load %93 : !llvm.ptr -> i64
      %128 = llvm.getelementptr %53[%127] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %126 = llvm.load %128 : !llvm.ptr -> i32
      %129 = arith.extsi %126 : i32 to i64
      %130 = llvm.load %93 : !llvm.ptr -> i64
      %131 = arith.muli %129, %130 : i64
      %132 = arith.remsi %131, %36 : i64
      %133 = arith.trunci %132 : i64 to i32
      %134 = llvm.load %93 : !llvm.ptr -> i64
      %135 = arith.constant 1 : i32
      %137 = arith.extsi %135 : i32 to i64
      %136 = arith.subi %134, %137 : i64
      %138 = llvm.getelementptr %53[%136] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %133, %138 : i32, !llvm.ptr
      %139 = llvm.load %93 : !llvm.ptr -> i64
      %140 = arith.constant 1 : i32
      %142 = arith.extsi %140 : i32 to i64
      %141 = arith.subi %139, %142 : i64
      llvm.store %141, %93 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %143 = arith.constant 1 : i32
    %144 = arith.extsi %143 : i32 to i64
    %145 = llvm.mlir.constant(1 : i64) : i64
    %146 = llvm.alloca %145 x i64 : (i64) -> !llvm.ptr
    llvm.store %144, %146 : i64, !llvm.ptr
    %147 = arith.constant 1 : i32
    %148 = arith.extsi %147 : i32 to i64
    %149 = llvm.mlir.constant(1 : i64) : i64
    %150 = llvm.alloca %149 x i64 : (i64) -> !llvm.ptr
    llvm.store %148, %150 : i64, !llvm.ptr
    %151 = arith.constant 0 : i32
    %152 = arith.extsi %151 : i32 to i64
    llvm.store %152, %93 : i64, !llvm.ptr
    cf.br ^bb15
    ^bb15:
    %153 = llvm.load %93 : !llvm.ptr -> i64
    %154 = arith.cmpi sle, %153, %34 : i64
    cf.cond_br %154, ^bb16, ^bb17
    ^bb16:
      %155 = llvm.load %93 : !llvm.ptr -> i64
      %156 = arith.constant 0 : i32
      %158 = arith.extsi %156 : i32 to i64
      %157 = arith.cmpi sgt, %155, %158 : i64
      cf.cond_br %157, ^bb18, ^bb19
      ^bb18:
        %159 = llvm.load %146 : !llvm.ptr -> i64
        %160 = arith.muli %159, %37 : i64
        %161 = arith.remsi %160, %36 : i64
        llvm.store %161, %146 : i64, !llvm.ptr
        %162 = llvm.load %150 : !llvm.ptr -> i64
        %163 = arith.muli %162, %45 : i64
        %164 = arith.remsi %163, %36 : i64
        llvm.store %164, %150 : i64, !llvm.ptr
        cf.br ^bb20
      ^bb19:
        cf.br ^bb20
      ^bb20:
      %165 = llvm.load %146 : !llvm.ptr -> i64
      %167 = llvm.load %93 : !llvm.ptr -> i64
      %168 = llvm.getelementptr %53[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %166 = llvm.load %168 : !llvm.ptr -> i32
      %169 = arith.extsi %166 : i32 to i64
      %170 = arith.muli %165, %169 : i64
      %171 = arith.remsi %170, %36 : i64
      %172 = arith.trunci %171 : i64 to i32
      %173 = llvm.load %93 : !llvm.ptr -> i64
      %174 = llvm.getelementptr %59[%173] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %172, %174 : i32, !llvm.ptr
      %175 = llvm.load %150 : !llvm.ptr -> i64
      %177 = llvm.load %93 : !llvm.ptr -> i64
      %178 = llvm.getelementptr %53[%177] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %176 = llvm.load %178 : !llvm.ptr -> i32
      %179 = arith.extsi %176 : i32 to i64
      %180 = arith.muli %175, %179 : i64
      %181 = arith.remsi %180, %36 : i64
      %182 = arith.trunci %181 : i64 to i32
      %183 = llvm.load %93 : !llvm.ptr -> i64
      %184 = llvm.getelementptr %65[%183] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %182, %184 : i32, !llvm.ptr
      %185 = llvm.load %93 : !llvm.ptr -> i64
      %186 = arith.constant 1 : i32
      %188 = arith.extsi %186 : i32 to i64
      %187 = arith.addi %185, %188 : i64
      llvm.store %187, %93 : i64, !llvm.ptr
      cf.br ^bb15
    ^bb17:
    func.call @free(%53) : (!llvm.ptr) -> ()
    %190 = arith.constant 0 : i32
    %191 = arith.extsi %190 : i32 to i64
    %192 = llvm.mlir.constant(1 : i64) : i64
    %193 = llvm.alloca %192 x i64 : (i64) -> !llvm.ptr
    llvm.store %191, %193 : i64, !llvm.ptr
    %194 = arith.constant 2 : i32
    %195 = arith.extsi %194 : i32 to i64
    %196 = llvm.mlir.constant(1 : i64) : i64
    %197 = llvm.alloca %196 x i64 : (i64) -> !llvm.ptr
    llvm.store %195, %197 : i64, !llvm.ptr
    cf.br ^bb21
    ^bb21:
    %198 = llvm.load %197 : !llvm.ptr -> i64
    %199 = arith.cmpi sle, %198, %34 : i64
    cf.cond_br %199, ^bb22, ^bb23
    ^bb22:
      %200 = llvm.load %197 : !llvm.ptr -> i64
      %201 = arith.divsi %34, %200 : i64
      %202 = llvm.load %197 : !llvm.ptr -> i64
      %203 = arith.constant 1 : i32
      %205 = arith.extsi %203 : i32 to i64
      %204 = arith.subi %202, %205 : i64
      %206 = llvm.mlir.constant(1 : i64) : i64
      %207 = llvm.alloca %206 x i64 : (i64) -> !llvm.ptr
      llvm.store %34, %207 : i64, !llvm.ptr
      %208 = llvm.mlir.constant(1 : i64) : i64
      %209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
      llvm.store %34, %209 : i64, !llvm.ptr
      %210 = arith.constant 0 : 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
      %214 = arith.constant 0 : i32
      %215 = arith.extsi %214 : i32 to i64
      %216 = llvm.mlir.constant(1 : i64) : i64
      %217 = llvm.alloca %216 x i64 : (i64) -> !llvm.ptr
      llvm.store %215, %217 : i64, !llvm.ptr
      cf.br ^bb24
      ^bb24:
      %218 = llvm.load %217 : !llvm.ptr -> i64
      %219 = arith.cmpi slt, %218, %201 : i64
      cf.cond_br %219, ^bb25, ^bb26
      ^bb25:
        %221 = llvm.load %217 : !llvm.ptr -> i64
        %222 = llvm.getelementptr %65[%221] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %220 = llvm.load %222 : !llvm.ptr -> i32
        %223 = arith.extsi %220 : i32 to i64
        %225 = llvm.load %209 : !llvm.ptr -> i64
        %226 = llvm.getelementptr %47[%225] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %224 = llvm.load %226 : !llvm.ptr -> i32
        %227 = arith.extsi %224 : i32 to i64
        %229 = llvm.load %207 : !llvm.ptr -> i64
        %230 = llvm.getelementptr %59[%229] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %228 = llvm.load %230 : !llvm.ptr -> i32
        %231 = arith.extsi %228 : i32 to i64
        %232 = arith.muli %227, %231 : i64
        %233 = arith.remsi %232, %36 : i64
        %234 = llvm.load %213 : !llvm.ptr -> i64
        %235 = arith.muli %233, %223 : i64
        %236 = arith.remsi %235, %36 : i64
        %237 = arith.addi %234, %236 : i64
        llvm.store %237, %213 : i64, !llvm.ptr
        %239 = llvm.load %209 : !llvm.ptr -> i64
        %240 = llvm.load %197 : !llvm.ptr -> i64
        %241 = arith.subi %239, %240 : i64
        %242 = llvm.getelementptr %47[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %238 = llvm.load %242 : !llvm.ptr -> i32
        %243 = arith.extsi %238 : i32 to i64
        %245 = llvm.load %207 : !llvm.ptr -> i64
        %246 = llvm.load %197 : !llvm.ptr -> i64
        %247 = arith.subi %245, %246 : i64
        %248 = llvm.getelementptr %59[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %244 = llvm.load %248 : !llvm.ptr -> i32
        %249 = arith.extsi %244 : i32 to i64
        %250 = arith.muli %243, %249 : i64
        %251 = arith.remsi %250, %36 : i64
        %252 = llvm.load %213 : !llvm.ptr -> i64
        %253 = arith.muli %251, %223 : i64
        %254 = arith.remsi %253, %36 : i64
        %255 = arith.subi %252, %254 : i64
        llvm.store %255, %213 : i64, !llvm.ptr
        %256 = llvm.load %207 : !llvm.ptr -> i64
        %257 = llvm.load %197 : !llvm.ptr -> i64
        %258 = arith.subi %256, %257 : i64
        llvm.store %258, %207 : i64, !llvm.ptr
        %259 = llvm.load %209 : !llvm.ptr -> i64
        %260 = arith.subi %259, %204 : i64
        llvm.store %260, %209 : i64, !llvm.ptr
        %261 = llvm.load %217 : !llvm.ptr -> i64
        %262 = arith.constant 1 : i32
        %264 = arith.extsi %262 : i32 to i64
        %263 = arith.addi %261, %264 : i64
        llvm.store %263, %217 : i64, !llvm.ptr
        cf.br ^bb24
      ^bb26:
      %266 = llvm.load %209 : !llvm.ptr -> i64
      %267 = llvm.getelementptr %47[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %265 = llvm.load %267 : !llvm.ptr -> i32
      %268 = arith.extsi %265 : i32 to i64
      %270 = llvm.load %207 : !llvm.ptr -> i64
      %271 = llvm.getelementptr %59[%270] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %269 = llvm.load %271 : !llvm.ptr -> i32
      %272 = arith.extsi %269 : i32 to i64
      %273 = arith.muli %268, %272 : i64
      %274 = arith.remsi %273, %36 : i64
      %275 = llvm.load %213 : !llvm.ptr -> i64
      %277 = llvm.getelementptr %65[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %276 = llvm.load %277 : !llvm.ptr -> i32
      %278 = arith.extsi %276 : i32 to i64
      %279 = arith.muli %274, %278 : i64
      %280 = arith.remsi %279, %36 : i64
      %281 = arith.addi %275, %280 : i64
      llvm.store %281, %213 : i64, !llvm.ptr
      %282 = llvm.load %193 : !llvm.ptr -> i64
      %283 = llvm.load %213 : !llvm.ptr -> i64
      %284 = arith.remsi %283, %36 : i64
      %285 = arith.addi %282, %284 : i64
      llvm.store %285, %193 : i64, !llvm.ptr
      %286 = llvm.load %197 : !llvm.ptr -> i64
      %287 = arith.constant 1023 : i32
      %289 = arith.extsi %287 : i32 to i64
      %288 = arith.andi %286, %289 : i64
      %290 = arith.constant 0 : i32
      %292 = arith.extsi %290 : i32 to i64
      %291 = arith.cmpi eq, %288, %292 : i64
      cf.cond_br %291, ^bb27, ^bb28
      ^bb27:
        %293 = llvm.load %193 : !llvm.ptr -> i64
        %294 = arith.remsi %293, %36 : i64
        llvm.store %294, %193 : i64, !llvm.ptr
        cf.br ^bb29
      ^bb28:
        cf.br ^bb29
      ^bb29:
      %295 = llvm.load %197 : !llvm.ptr -> i64
      %296 = arith.constant 1 : i32
      %298 = arith.extsi %296 : i32 to i64
      %297 = arith.addi %295, %298 : i64
      llvm.store %297, %197 : i64, !llvm.ptr
      cf.br ^bb21
    ^bb23:
    %299 = llvm.load %193 : !llvm.ptr -> i64
    %300 = arith.remsi %299, %36 : i64
    llvm.store %300, %193 : i64, !llvm.ptr
    %301 = llvm.load %193 : !llvm.ptr -> i64
    %302 = arith.constant 0 : i32
    %304 = arith.extsi %302 : i32 to i64
    %303 = arith.cmpi slt, %301, %304 : i64
    cf.cond_br %303, ^bb30, ^bb31
    ^bb30:
      %305 = llvm.load %193 : !llvm.ptr -> i64
      %306 = arith.addi %305, %36 : i64
      llvm.store %306, %193 : i64, !llvm.ptr
      cf.br ^bb32
    ^bb31:
      cf.br ^bb32
    ^bb32:
    %308 = arith.constant 1 : i32
    %310 = arith.extsi %308 : i32 to i64
    %309 = arith.addi %34, %310 : i64
    %307 = func.call @mod_pow(%37, %309, %36) : (i64, i64, i64) -> i64
    %311 = llvm.load %193 : !llvm.ptr -> i64
    %312 = arith.subi %307, %311 : i64
    %313 = arith.remsi %312, %36 : i64
    %314 = arith.constant 0 : i32
    %316 = arith.extsi %314 : i32 to i64
    %315 = arith.cmpi slt, %313, %316 : i64
    %317 = scf.if %315 -> (i64) {
      %318 = arith.addi %313, %36 : i64
      scf.yield %318 : i64
    } else {
      scf.yield %313 : i64
    }
    %319 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %320 = llvm.call @printf(%319, %317) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%65) : (!llvm.ptr) -> ()
    func.call @free(%59) : (!llvm.ptr) -> ()
    func.call @free(%47) : (!llvm.ptr) -> ()
    %324 = arith.constant 0 : i32
    func.return %324 : i32
  }
}