Problem 873
Words with Gaps: W(10^6, 10^7, 10^8) mod 1e9+7.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | ? |
|---|
| Space complexity | O(1) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 873
# Words with Gaps: W(10^6, 10^7, 10^8) mod 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const MOD: i64 = 1000000007
function modpow(base: i64, exp: i64, mod: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = base % mod
if b < 0 { b = b + mod }
let mut e: i64 = exp
while e > 0 {
if (e & 1) != 0 {
r = ((r as i128) * b % mod) as i64
}
b = ((b as i128) * b % mod) as i64
e = e >> 1
}
return r
}
# Batch modular inverses of [start..end] inclusive.
# invs[i] = (start+i)^(-1) mod mod.
function batch_inverses(start: i64, end: i64, mod: i64, invs: ptr<i64>) -> void {
let length: i64 = end - start + 1
let pref: ptr<i64> = malloc((length + 1) * 8)
pref[0] = 1
for i in 0..length {
pref[i + 1] = ((pref[i] as i128) * (start + i) % mod) as i64
}
let mut inv_total: i64 = modpow(pref[length], mod - 2, mod)
let mut j: i64 = length - 1
while j >= 0 {
let x: i64 = start + j
invs[j] = ((inv_total as i128) * pref[j] % mod) as i64
inv_total = ((inv_total as i128) * x % mod) as i64
j = j - 1
}
free(pref)
}
function main() -> i32 {
let mut p: i64 = 1000000
let mut q: i64 = 10000000
let r: i64 = 100000000
let mod: i64 = MOD
# Symmetry: ensure p <= q
if p > q {
let tmp: i64 = p
p = q
q = tmp
}
let k: i64 = p + q
let tmax_transitions: i64 = 2 * p
if p == q { tmax_transitions = tmax_transitions - 1 }
let mut tmax: i64 = tmax_transitions
if r / 2 < tmax { tmax = r / 2 }
if tmax <= 0 {
printf("%lld\n", 0 as i64)
return 0
}
# Precompute inverses 1..p+1
let inv_small: ptr<i64> = malloc((p + 2) * 8)
inv_small[1] = 1
for i in 2..(p + 2) {
inv_small[i] = (mod - (mod / i) * inv_small[mod % i] % mod) % mod
}
# Precompute C(p-1, x) for x=0..p-1
let choose_p: ptr<i64> = malloc(p * 8)
choose_p[0] = 1
let mut c: i64 = 1
let n1: i64 = p - 1
for x in 0..(p - 1) {
c = ((c as i128) * (n1 - x) % mod) as i64
c = ((c as i128) * inv_small[x + 1] % mod) as i64
choose_p[x + 1] = c
}
# Precompute C(q-1, x) for x=0..p
let choose_q: ptr<i64> = malloc((p + 1) * 8)
choose_q[0] = 1
let mut c2: i64 = 1
let n2: i64 = q - 1
for x2 in 0..p {
c2 = ((c2 as i128) * (n2 - x2) % mod) as i64
c2 = ((c2 as i128) * inv_small[x2 + 1] % mod) as i64
choose_q[x2 + 1] = c2
}
# Batch inverses for the binomial recurrence
let N0: i64 = r + k
let lowest_needed: i64 = N0 - 2 * (tmax - 1) - 1
let inv_base: i64 = lowest_needed
let inv_end: i64 = N0
let inv_range: ptr<i64> = malloc((inv_end - inv_base + 1) * 8)
batch_inverses(inv_base, inv_end, mod, inv_range)
# Compute B_0 = C(r+k, k) = prod_{i=1..k} (r+i)/i
let mut num: i64 = 1
let mut den: i64 = 1
for i2 in 1..(k + 1) {
num = ((num as i128) * (r + i2) % mod) as i64
den = ((den as i128) * i2 % mod) as i64
}
let mut B: i64 = ((num as i128) * modpow(den, mod - 2, mod) % mod) as i64
let mut ans: i64 = 0
let mut n_total: i64 = N0
let mut n_gap: i64 = r
for t in 1..(tmax + 1) {
# Update B from t-1 to t
let mut ratio: i64 = ((n_gap % mod) as i128 * ((n_gap - 1) % mod) % mod) as i64
ratio = ((ratio as i128) * inv_range[n_total - inv_base] % mod) as i64
ratio = ((ratio as i128) * inv_range[n_total - 1 - inv_base] % mod) as i64
B = ((B as i128) * ratio % mod) as i64
n_total = n_total - 2
n_gap = n_gap - 2
# Count AB-strings with exactly t transitions
let a_runs: i64 = (t + 2) / 2
let b_runs: i64 = (t + 1) / 2
let mut count_t: i64 = 0
if a_runs <= p && b_runs <= q {
count_t = ((choose_p[a_runs - 1] as i128) * choose_q[b_runs - 1] % mod) as i64
}
let a_runs2: i64 = (t + 1) / 2
let b_runs2: i64 = (t + 2) / 2
if a_runs2 <= p && b_runs2 <= q {
count_t = (count_t + ((choose_p[a_runs2 - 1] as i128) * choose_q[b_runs2 - 1] % mod) as i64) % mod
}
ans = (ans + ((count_t as i128) * B % mod) as i64) % mod
}
printf("%lld\n", ans)
free(inv_small)
free(choose_p)
free(choose_q)
free(inv_range)
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 modpow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
void batch_inverses_i64_i64_i64_ptr_i64(int64_t start, int64_t end, int64_t mod, int64_t* invs);
int32_t main(void);
static const int64_t MOD = 1000000007;
int64_t modpow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
if (b < 0) {
b = (b + mod);
}
int64_t e = exp;
while (e > 0) {
if ((e & 1) != 0) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * b)), (mod))));
}
b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(b)) * b)), (mod))));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
void batch_inverses_i64_i64_i64_ptr_i64(int64_t start, int64_t end, int64_t mod, int64_t* invs) {
int64_t length = ((end - start) + 1);
int64_t* pref = (int64_t*)(malloc(((length + 1) * 8)));
pref[0] = 1;
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= length) ? i < length : i > length; i += (0 <= length) ? 1 : -1) {
pref[(i + 1)] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(pref[i])) * (start + i))), (mod))));
}
int64_t inv_total = modpow_i64_i64_i64(pref[length], (mod - 2), mod);
int64_t j = (length - 1);
while (j >= 0) {
int64_t x = (start + j);
invs[j] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(inv_total)) * pref[j])), (mod))));
inv_total = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(inv_total)) * x)), (mod))));
j = (j - 1);
}
free(pref);
}
int32_t main(void) {
int64_t p = 1000000;
int64_t q = 10000000;
int64_t r = 100000000;
int64_t mod = MOD;
if (p > q) {
int64_t tmp = p;
p = q;
q = tmp;
}
int64_t k = (p + q);
int64_t tmax_transitions = (2 * p);
if (p == q) {
tmax_transitions = (tmax_transitions - 1);
}
int64_t tmax = tmax_transitions;
if (FLOW_CHECKED_DIV((r), (2)) < tmax) {
tmax = FLOW_CHECKED_DIV((r), (2));
}
if (tmax <= 0) {
printf("%lld\n", ((int64_t)(0)));
return 0;
}
int64_t* inv_small = (int64_t*)(malloc(((p + 2) * 8)));
inv_small[1] = 1;
int32_t __flow_step_2 = 1;
for (int32_t i = 2; (2 <= (p + 2)) ? i < (p + 2) : i > (p + 2); i += (2 <= (p + 2)) ? 1 : -1) {
inv_small[i] = FLOW_CHECKED_MOD(((mod - FLOW_CHECKED_MOD(((FLOW_CHECKED_DIV((mod), (i)) * inv_small[FLOW_CHECKED_MOD((mod), (i))])), (mod)))), (mod));
}
int64_t* choose_p = (int64_t*)(malloc((p * 8)));
choose_p[0] = 1;
int64_t c = 1;
int64_t n1 = (p - 1);
int32_t __flow_step_3 = 1;
for (int32_t x = 0; (0 <= (p - 1)) ? x < (p - 1) : x > (p - 1); x += (0 <= (p - 1)) ? 1 : -1) {
c = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(c)) * (n1 - x))), (mod))));
c = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(c)) * inv_small[(x + 1)])), (mod))));
choose_p[(x + 1)] = c;
}
int64_t* choose_q = (int64_t*)(malloc(((p + 1) * 8)));
choose_q[0] = 1;
int64_t c2 = 1;
int64_t n2 = (q - 1);
int32_t __flow_step_4 = 1;
for (int32_t x2 = 0; (0 <= p) ? x2 < p : x2 > p; x2 += (0 <= p) ? 1 : -1) {
c2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(c2)) * (n2 - x2))), (mod))));
c2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(c2)) * inv_small[(x2 + 1)])), (mod))));
choose_q[(x2 + 1)] = c2;
}
int64_t N0 = (r + k);
int64_t lowest_needed = ((N0 - (2 * (tmax - 1))) - 1);
int64_t inv_base = lowest_needed;
int64_t inv_end = N0;
int64_t* inv_range = (int64_t*)(malloc((((inv_end - inv_base) + 1) * 8)));
batch_inverses_i64_i64_i64_ptr_i64(inv_base, inv_end, mod, inv_range);
int64_t num = 1;
int64_t den = 1;
int32_t __flow_step_5 = 1;
for (int32_t i2 = 1; (1 <= (k + 1)) ? i2 < (k + 1) : i2 > (k + 1); i2 += (1 <= (k + 1)) ? 1 : -1) {
num = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(num)) * (r + i2))), (mod))));
den = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(den)) * i2)), (mod))));
}
int64_t B = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(num)) * modpow_i64_i64_i64(den, (mod - 2), mod))), (mod))));
int64_t ans = 0;
int64_t n_total = N0;
int64_t n_gap = r;
int32_t __flow_step_6 = 1;
for (int32_t t = 1; (1 <= (tmax + 1)) ? t < (tmax + 1) : t > (tmax + 1); t += (1 <= (tmax + 1)) ? 1 : -1) {
int64_t ratio = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD((n_gap), (mod)))) * FLOW_CHECKED_MOD(((n_gap - 1)), (mod)))), (mod))));
ratio = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(ratio)) * inv_range[(n_total - inv_base)])), (mod))));
ratio = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(ratio)) * inv_range[((n_total - 1) - inv_base)])), (mod))));
B = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(B)) * ratio)), (mod))));
n_total = (n_total - 2);
n_gap = (n_gap - 2);
int64_t a_runs = FLOW_CHECKED_DIV(((t + 2)), (2));
int64_t b_runs = FLOW_CHECKED_DIV(((t + 1)), (2));
int64_t count_t = 0;
if ((a_runs <= p && b_runs <= q)) {
count_t = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(choose_p[(a_runs - 1)])) * choose_q[(b_runs - 1)])), (mod))));
}
int64_t a_runs2 = FLOW_CHECKED_DIV(((t + 1)), (2));
int64_t b_runs2 = FLOW_CHECKED_DIV(((t + 2)), (2));
if ((a_runs2 <= p && b_runs2 <= q)) {
count_t = FLOW_CHECKED_MOD(((count_t + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(choose_p[(a_runs2 - 1)])) * choose_q[(b_runs2 - 1)])), (mod)))))), (mod));
}
ans = FLOW_CHECKED_MOD(((ans + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(count_t)) * B)), (mod)))))), (mod));
}
printf("%lld\n", ans);
free(inv_small);
free(choose_p);
free(choose_q);
free(inv_range);
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
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
func.func @modpow(%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:
%13 = llvm.mlir.constant(1 : i64) : i64
%14 = llvm.alloca %13 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %14 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%15 = llvm.load %14 : !llvm.ptr -> i64
%16 = arith.constant 0 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.cmpi sgt, %15, %18 : i64
cf.cond_br %17, ^bb4, ^bb5
^bb4:
%19 = llvm.load %14 : !llvm.ptr -> i64
%20 = arith.constant 1 : i32
%22 = arith.extsi %20 : i32 to i64
%21 = arith.andi %19, %22 : i64
%23 = arith.constant 0 : i32
%25 = arith.extsi %23 : i32 to i64
%24 = arith.cmpi ne, %21, %25 : i64
cf.cond_br %24, ^bb6, ^bb7
^bb6:
%26 = llvm.load %3 : !llvm.ptr -> i64
%27 = arith.extsi %26 : i64 to i128
%28 = llvm.load %6 : !llvm.ptr -> i64
%30 = arith.trunci %27 : i128 to i64
%29 = arith.muli %30, %28 : i64
%31 = arith.remsi %29, %arg2 : i64
llvm.store %31, %3 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%32 = llvm.load %6 : !llvm.ptr -> i64
%33 = arith.extsi %32 : i64 to i128
%34 = llvm.load %6 : !llvm.ptr -> i64
%36 = arith.trunci %33 : i128 to i64
%35 = arith.muli %36, %34 : i64
%37 = arith.remsi %35, %arg2 : i64
llvm.store %37, %6 : i64, !llvm.ptr
%38 = llvm.load %14 : !llvm.ptr -> i64
%39 = arith.constant 1 : i32
%41 = arith.extsi %39 : i32 to i64
%40 = arith.shrsi %38, %41 : i64
llvm.store %40, %14 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%42 = llvm.load %3 : !llvm.ptr -> i64
func.return %42 : i64
}
func.func @batch_inverses(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr) -> () {
%43 = arith.subi %arg1, %arg0 : i64
%44 = arith.constant 1 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.addi %43, %46 : i64
%48 = arith.constant 1 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.addi %45, %50 : i64
%51 = arith.constant 8 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.muli %49, %53 : i64
%47 = func.call @malloc(%52) : (i64) -> !llvm.ptr
%54 = arith.constant 1 : i32
%55 = arith.constant 0 : i32
%56 = arith.extsi %54 : i32 to i64
%57 = arith.extsi %55 : i32 to i64
%58 = llvm.getelementptr %47[%57] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %56, %58 : i64, !llvm.ptr
%59 = arith.constant 0 : i32
%60 = arith.index_cast %59 : i32 to index
%61 = arith.index_cast %45 : i32 to index
%63 = arith.constant 1 : index
%64 = arith.constant -1 : index
%65 = arith.cmpi sle, %60, %61 : index
%62 = arith.select %65, %63, %64 : index
cf.br ^bb9(%60 : index)
^bb9(%66: index):
%67 = arith.cmpi slt, %66, %61 : index
%68 = arith.cmpi sgt, %66, %61 : index
%69 = arith.select %65, %67, %68 : i1
cf.cond_br %69, ^bb10(%66 : index), ^bb11(%66 : index)
^bb10(%70: index):
%72 = arith.index_cast %70 : index to i64
%73 = llvm.getelementptr %47[%72] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%71 = llvm.load %73 : !llvm.ptr -> i64
%74 = arith.extsi %71 : i64 to i128
%76 = arith.trunci %arg0 : i64 to i32
%77 = arith.index_cast %70 : index to i32
%75 = arith.addi %76, %77 : i32
%79 = arith.trunci %74 : i128 to i64
%80 = arith.extsi %75 : i32 to i64
%78 = arith.muli %79, %80 : i64
%81 = arith.remsi %78, %arg2 : i64
%82 = arith.constant 1 : i32
%84 = arith.index_cast %70 : index to i32
%83 = arith.addi %84, %82 : i32
%85 = arith.extsi %83 : i32 to i64
%86 = llvm.getelementptr %47[%85] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %81, %86 : i64, !llvm.ptr
%87 = arith.addi %70, %62 : index
cf.br ^bb9(%87 : index)
^bb11(%88: index):
%91 = llvm.getelementptr %47[%45] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%90 = llvm.load %91 : !llvm.ptr -> i64
%92 = arith.constant 2 : i32
%94 = arith.extsi %92 : i32 to i64
%93 = arith.subi %arg2, %94 : i64
%89 = func.call @modpow(%90, %93, %arg2) : (i64, i64, i64) -> i64
%95 = llvm.mlir.constant(1 : i64) : i64
%96 = llvm.alloca %95 x i64 : (i64) -> !llvm.ptr
llvm.store %89, %96 : i64, !llvm.ptr
%97 = arith.constant 1 : i32
%99 = arith.extsi %97 : i32 to i64
%98 = arith.subi %45, %99 : i64
%100 = llvm.mlir.constant(1 : i64) : i64
%101 = llvm.alloca %100 x i64 : (i64) -> !llvm.ptr
llvm.store %98, %101 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%102 = llvm.load %101 : !llvm.ptr -> i64
%103 = arith.constant 0 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.cmpi sge, %102, %105 : i64
cf.cond_br %104, ^bb13, ^bb14
^bb13:
%106 = llvm.load %101 : !llvm.ptr -> i64
%107 = arith.addi %arg0, %106 : i64
%108 = llvm.load %96 : !llvm.ptr -> i64
%109 = arith.extsi %108 : i64 to i128
%111 = llvm.load %101 : !llvm.ptr -> i64
%112 = llvm.getelementptr %47[%111] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%110 = llvm.load %112 : !llvm.ptr -> i64
%114 = arith.trunci %109 : i128 to i64
%113 = arith.muli %114, %110 : i64
%115 = arith.remsi %113, %arg2 : i64
%116 = llvm.load %101 : !llvm.ptr -> i64
%117 = llvm.getelementptr %arg3[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %115, %117 : i64, !llvm.ptr
%118 = llvm.load %96 : !llvm.ptr -> i64
%119 = arith.extsi %118 : i64 to i128
%121 = arith.trunci %119 : i128 to i64
%120 = arith.muli %121, %107 : i64
%122 = arith.remsi %120, %arg2 : i64
llvm.store %122, %96 : i64, !llvm.ptr
%123 = llvm.load %101 : !llvm.ptr -> i64
%124 = arith.constant 1 : i32
%126 = arith.extsi %124 : i32 to i64
%125 = arith.subi %123, %126 : i64
llvm.store %125, %101 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
func.call @free(%47) : (!llvm.ptr) -> ()
func.return
}
func.func @main() -> i32 {
%128 = arith.constant 1000000 : i32
%129 = arith.extsi %128 : i32 to i64
%130 = llvm.mlir.constant(1 : i64) : i64
%131 = llvm.alloca %130 x i64 : (i64) -> !llvm.ptr
llvm.store %129, %131 : i64, !llvm.ptr
%132 = arith.constant 10000000 : i32
%133 = arith.extsi %132 : i32 to i64
%134 = llvm.mlir.constant(1 : i64) : i64
%135 = llvm.alloca %134 x i64 : (i64) -> !llvm.ptr
llvm.store %133, %135 : i64, !llvm.ptr
%136 = arith.constant 100000000 : i32
%137 = arith.extsi %136 : i32 to i64
%138 = llvm.mlir.addressof @MOD : !llvm.ptr
%139 = llvm.load %138 : !llvm.ptr -> i64
%140 = llvm.load %131 : !llvm.ptr -> i64
%141 = llvm.load %135 : !llvm.ptr -> i64
%142 = arith.cmpi sgt, %140, %141 : i64
cf.cond_br %142, ^bb15, ^bb16
^bb15:
%143 = llvm.load %131 : !llvm.ptr -> i64
%144 = llvm.load %135 : !llvm.ptr -> i64
llvm.store %144, %131 : i64, !llvm.ptr
llvm.store %143, %135 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%145 = llvm.load %131 : !llvm.ptr -> i64
%146 = llvm.load %135 : !llvm.ptr -> i64
%147 = arith.addi %145, %146 : i64
%148 = arith.constant 2 : i32
%149 = llvm.load %131 : !llvm.ptr -> i64
%151 = arith.extsi %148 : i32 to i64
%150 = arith.muli %151, %149 : i64
%152 = llvm.load %131 : !llvm.ptr -> i64
%153 = llvm.load %135 : !llvm.ptr -> i64
%154 = arith.cmpi eq, %152, %153 : i64
%155 = scf.if %154 -> (i64) {
%156 = arith.constant 1 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.subi %150, %158 : i64
scf.yield %157 : i64
} else {
scf.yield %150 : i64
}
%159 = llvm.mlir.constant(1 : i64) : i64
%160 = llvm.alloca %159 x i64 : (i64) -> !llvm.ptr
llvm.store %155, %160 : i64, !llvm.ptr
%161 = arith.constant 2 : i32
%163 = arith.extsi %161 : i32 to i64
%162 = arith.divsi %137, %163 : i64
%164 = llvm.load %160 : !llvm.ptr -> i64
%165 = arith.cmpi slt, %162, %164 : i64
cf.cond_br %165, ^bb18, ^bb19
^bb18:
%166 = arith.constant 2 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.divsi %137, %168 : i64
llvm.store %167, %160 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%169 = llvm.load %160 : !llvm.ptr -> i64
%170 = arith.constant 0 : i32
%172 = arith.extsi %170 : i32 to i64
%171 = arith.cmpi sle, %169, %172 : i64
cf.cond_br %171, ^bb21, ^bb22
^bb21:
%173 = llvm.mlir.addressof @str_0 : !llvm.ptr
%174 = arith.constant 0 : i32
%175 = arith.extsi %174 : i32 to i64
%176 = llvm.call @printf(%173, %175) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%177 = arith.constant 0 : i32
func.return %177 : i32
^bb22:
cf.br ^bb23
^bb23:
%179 = llvm.load %131 : !llvm.ptr -> i64
%180 = arith.constant 2 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.addi %179, %182 : i64
%183 = arith.constant 8 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.muli %181, %185 : i64
%178 = func.call @malloc(%184) : (i64) -> !llvm.ptr
%186 = arith.constant 1 : i32
%187 = arith.constant 1 : i32
%188 = arith.extsi %186 : i32 to i64
%189 = arith.extsi %187 : i32 to i64
%190 = llvm.getelementptr %178[%189] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %188, %190 : i64, !llvm.ptr
%191 = arith.constant 2 : i32
%192 = llvm.load %131 : !llvm.ptr -> i64
%193 = arith.constant 2 : i32
%195 = arith.extsi %193 : i32 to i64
%194 = arith.addi %192, %195 : i64
%196 = arith.index_cast %191 : i32 to index
%197 = arith.index_cast %194 : i32 to index
%199 = arith.constant 1 : index
%200 = arith.constant -1 : index
%201 = arith.cmpi sle, %196, %197 : index
%198 = arith.select %201, %199, %200 : index
cf.br ^bb24(%196 : index)
^bb24(%202: index):
%203 = arith.cmpi slt, %202, %197 : index
%204 = arith.cmpi sgt, %202, %197 : index
%205 = arith.select %201, %203, %204 : i1
cf.cond_br %205, ^bb25(%202 : index), ^bb26(%202 : index)
^bb25(%206: index):
%208 = arith.trunci %139 : i64 to i32
%209 = arith.index_cast %206 : index to i32
%207 = arith.divsi %208, %209 : i32
%212 = arith.trunci %139 : i64 to i32
%213 = arith.index_cast %206 : index to i32
%211 = arith.remsi %212, %213 : i32
%214 = arith.extsi %211 : i32 to i64
%215 = llvm.getelementptr %178[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%210 = llvm.load %215 : !llvm.ptr -> i64
%217 = arith.extsi %207 : i32 to i64
%216 = arith.muli %217, %210 : i64
%218 = arith.remsi %216, %139 : i64
%219 = arith.subi %139, %218 : i64
%220 = arith.remsi %219, %139 : i64
%221 = arith.index_cast %206 : index to i64
%222 = llvm.getelementptr %178[%221] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %220, %222 : i64, !llvm.ptr
%223 = arith.addi %206, %198 : index
cf.br ^bb24(%223 : index)
^bb26(%224: index):
%226 = llvm.load %131 : !llvm.ptr -> i64
%227 = arith.constant 8 : i32
%229 = arith.extsi %227 : i32 to i64
%228 = arith.muli %226, %229 : i64
%225 = func.call @malloc(%228) : (i64) -> !llvm.ptr
%230 = arith.constant 1 : i32
%231 = arith.constant 0 : i32
%232 = arith.extsi %230 : i32 to i64
%233 = arith.extsi %231 : i32 to i64
%234 = llvm.getelementptr %225[%233] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %232, %234 : i64, !llvm.ptr
%235 = arith.constant 1 : i32
%236 = arith.extsi %235 : i32 to i64
%237 = llvm.mlir.constant(1 : i64) : i64
%238 = llvm.alloca %237 x i64 : (i64) -> !llvm.ptr
llvm.store %236, %238 : i64, !llvm.ptr
%239 = llvm.load %131 : !llvm.ptr -> i64
%240 = arith.constant 1 : i32
%242 = arith.extsi %240 : i32 to i64
%241 = arith.subi %239, %242 : i64
%243 = arith.constant 0 : i32
%244 = llvm.load %131 : !llvm.ptr -> i64
%245 = arith.constant 1 : i32
%247 = arith.extsi %245 : i32 to i64
%246 = arith.subi %244, %247 : i64
%248 = arith.index_cast %243 : i32 to index
%249 = arith.index_cast %246 : i32 to index
%251 = arith.constant 1 : index
%252 = arith.constant -1 : index
%253 = arith.cmpi sle, %248, %249 : index
%250 = arith.select %253, %251, %252 : index
cf.br ^bb27(%248 : index)
^bb27(%254: index):
%255 = arith.cmpi slt, %254, %249 : index
%256 = arith.cmpi sgt, %254, %249 : index
%257 = arith.select %253, %255, %256 : i1
cf.cond_br %257, ^bb28(%254 : index), ^bb29(%254 : index)
^bb28(%258: index):
%259 = llvm.load %238 : !llvm.ptr -> i64
%260 = arith.extsi %259 : i64 to i128
%262 = arith.trunci %241 : i64 to i32
%263 = arith.index_cast %258 : index to i32
%261 = arith.subi %262, %263 : i32
%265 = arith.trunci %260 : i128 to i64
%266 = arith.extsi %261 : i32 to i64
%264 = arith.muli %265, %266 : i64
%267 = arith.remsi %264, %139 : i64
llvm.store %267, %238 : i64, !llvm.ptr
%268 = llvm.load %238 : !llvm.ptr -> i64
%269 = arith.extsi %268 : i64 to i128
%271 = arith.constant 1 : i32
%273 = arith.index_cast %258 : index to i32
%272 = arith.addi %273, %271 : i32
%274 = arith.extsi %272 : i32 to i64
%275 = llvm.getelementptr %178[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%270 = llvm.load %275 : !llvm.ptr -> i64
%277 = arith.trunci %269 : i128 to i64
%276 = arith.muli %277, %270 : i64
%278 = arith.remsi %276, %139 : i64
llvm.store %278, %238 : i64, !llvm.ptr
%279 = llvm.load %238 : !llvm.ptr -> i64
%280 = arith.constant 1 : i32
%282 = arith.index_cast %258 : index to i32
%281 = arith.addi %282, %280 : i32
%283 = arith.extsi %281 : i32 to i64
%284 = llvm.getelementptr %225[%283] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %279, %284 : i64, !llvm.ptr
%285 = arith.addi %258, %250 : index
cf.br ^bb27(%285 : index)
^bb29(%286: index):
%288 = llvm.load %131 : !llvm.ptr -> i64
%289 = arith.constant 1 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.addi %288, %291 : i64
%292 = arith.constant 8 : i32
%294 = arith.extsi %292 : i32 to i64
%293 = arith.muli %290, %294 : i64
%287 = func.call @malloc(%293) : (i64) -> !llvm.ptr
%295 = arith.constant 1 : i32
%296 = arith.constant 0 : i32
%297 = arith.extsi %295 : i32 to i64
%298 = arith.extsi %296 : i32 to i64
%299 = llvm.getelementptr %287[%298] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %297, %299 : i64, !llvm.ptr
%300 = arith.constant 1 : i32
%301 = arith.extsi %300 : i32 to i64
%302 = llvm.mlir.constant(1 : i64) : i64
%303 = llvm.alloca %302 x i64 : (i64) -> !llvm.ptr
llvm.store %301, %303 : i64, !llvm.ptr
%304 = llvm.load %135 : !llvm.ptr -> i64
%305 = arith.constant 1 : i32
%307 = arith.extsi %305 : i32 to i64
%306 = arith.subi %304, %307 : i64
%308 = arith.constant 0 : i32
%309 = llvm.load %131 : !llvm.ptr -> i64
%310 = arith.index_cast %308 : i32 to index
%311 = arith.index_cast %309 : i32 to index
%313 = arith.constant 1 : index
%314 = arith.constant -1 : index
%315 = arith.cmpi sle, %310, %311 : index
%312 = arith.select %315, %313, %314 : index
cf.br ^bb30(%310 : index)
^bb30(%316: index):
%317 = arith.cmpi slt, %316, %311 : index
%318 = arith.cmpi sgt, %316, %311 : index
%319 = arith.select %315, %317, %318 : i1
cf.cond_br %319, ^bb31(%316 : index), ^bb32(%316 : index)
^bb31(%320: index):
%321 = llvm.load %303 : !llvm.ptr -> i64
%322 = arith.extsi %321 : i64 to i128
%324 = arith.trunci %306 : i64 to i32
%325 = arith.index_cast %320 : index to i32
%323 = arith.subi %324, %325 : i32
%327 = arith.trunci %322 : i128 to i64
%328 = arith.extsi %323 : i32 to i64
%326 = arith.muli %327, %328 : i64
%329 = arith.remsi %326, %139 : i64
llvm.store %329, %303 : i64, !llvm.ptr
%330 = llvm.load %303 : !llvm.ptr -> i64
%331 = arith.extsi %330 : i64 to i128
%333 = arith.constant 1 : i32
%335 = arith.index_cast %320 : index to i32
%334 = arith.addi %335, %333 : i32
%336 = arith.extsi %334 : i32 to i64
%337 = llvm.getelementptr %178[%336] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%332 = llvm.load %337 : !llvm.ptr -> i64
%339 = arith.trunci %331 : i128 to i64
%338 = arith.muli %339, %332 : i64
%340 = arith.remsi %338, %139 : i64
llvm.store %340, %303 : i64, !llvm.ptr
%341 = llvm.load %303 : !llvm.ptr -> i64
%342 = arith.constant 1 : i32
%344 = arith.index_cast %320 : index to i32
%343 = arith.addi %344, %342 : i32
%345 = arith.extsi %343 : i32 to i64
%346 = llvm.getelementptr %287[%345] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %341, %346 : i64, !llvm.ptr
%347 = arith.addi %320, %312 : index
cf.br ^bb30(%347 : index)
^bb32(%348: index):
%349 = arith.addi %137, %147 : i64
%350 = arith.constant 2 : i32
%351 = llvm.load %160 : !llvm.ptr -> i64
%352 = arith.constant 1 : i32
%354 = arith.extsi %352 : i32 to i64
%353 = arith.subi %351, %354 : i64
%356 = arith.extsi %350 : i32 to i64
%355 = arith.muli %356, %353 : i64
%357 = arith.subi %349, %355 : i64
%358 = arith.constant 1 : i32
%360 = arith.extsi %358 : i32 to i64
%359 = arith.subi %357, %360 : i64
%362 = arith.subi %349, %359 : i64
%363 = arith.constant 1 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.addi %362, %365 : i64
%366 = arith.constant 8 : i32
%368 = arith.extsi %366 : i32 to i64
%367 = arith.muli %364, %368 : i64
%361 = func.call @malloc(%367) : (i64) -> !llvm.ptr
func.call @batch_inverses(%359, %349, %139, %361) : (i64, i64, i64, !llvm.ptr) -> ()
%370 = arith.constant 1 : i32
%371 = arith.extsi %370 : i32 to i64
%372 = llvm.mlir.constant(1 : i64) : i64
%373 = llvm.alloca %372 x i64 : (i64) -> !llvm.ptr
llvm.store %371, %373 : i64, !llvm.ptr
%374 = arith.constant 1 : i32
%375 = arith.extsi %374 : i32 to i64
%376 = llvm.mlir.constant(1 : i64) : i64
%377 = llvm.alloca %376 x i64 : (i64) -> !llvm.ptr
llvm.store %375, %377 : i64, !llvm.ptr
%378 = arith.constant 1 : i32
%379 = arith.constant 1 : i32
%381 = arith.extsi %379 : i32 to i64
%380 = arith.addi %147, %381 : i64
%382 = arith.index_cast %378 : i32 to index
%383 = arith.index_cast %380 : i32 to index
%385 = arith.constant 1 : index
%386 = arith.constant -1 : index
%387 = arith.cmpi sle, %382, %383 : index
%384 = arith.select %387, %385, %386 : index
cf.br ^bb33(%382 : index)
^bb33(%388: index):
%389 = arith.cmpi slt, %388, %383 : index
%390 = arith.cmpi sgt, %388, %383 : index
%391 = arith.select %387, %389, %390 : i1
cf.cond_br %391, ^bb34(%388 : index), ^bb35(%388 : index)
^bb34(%392: index):
%393 = llvm.load %373 : !llvm.ptr -> i64
%394 = arith.extsi %393 : i64 to i128
%396 = arith.trunci %137 : i64 to i32
%397 = arith.index_cast %392 : index to i32
%395 = arith.addi %396, %397 : i32
%399 = arith.trunci %394 : i128 to i64
%400 = arith.extsi %395 : i32 to i64
%398 = arith.muli %399, %400 : i64
%401 = arith.remsi %398, %139 : i64
llvm.store %401, %373 : i64, !llvm.ptr
%402 = llvm.load %377 : !llvm.ptr -> i64
%403 = arith.extsi %402 : i64 to i128
%405 = arith.trunci %403 : i128 to i32
%406 = arith.index_cast %392 : index to i32
%404 = arith.muli %405, %406 : i32
%408 = arith.extsi %404 : i32 to i64
%407 = arith.remsi %408, %139 : i64
llvm.store %407, %377 : i64, !llvm.ptr
%409 = arith.addi %392, %384 : index
cf.br ^bb33(%409 : index)
^bb35(%410: index):
%411 = llvm.load %373 : !llvm.ptr -> i64
%412 = arith.extsi %411 : i64 to i128
%414 = llvm.load %377 : !llvm.ptr -> i64
%415 = arith.constant 2 : i32
%417 = arith.extsi %415 : i32 to i64
%416 = arith.subi %139, %417 : i64
%413 = func.call @modpow(%414, %416, %139) : (i64, i64, i64) -> i64
%419 = arith.trunci %412 : i128 to i64
%418 = arith.muli %419, %413 : i64
%420 = arith.remsi %418, %139 : i64
%421 = llvm.mlir.constant(1 : i64) : i64
%422 = llvm.alloca %421 x i64 : (i64) -> !llvm.ptr
llvm.store %420, %422 : i64, !llvm.ptr
%423 = arith.constant 0 : i32
%424 = arith.extsi %423 : i32 to i64
%425 = llvm.mlir.constant(1 : i64) : i64
%426 = llvm.alloca %425 x i64 : (i64) -> !llvm.ptr
llvm.store %424, %426 : i64, !llvm.ptr
%427 = llvm.mlir.constant(1 : i64) : i64
%428 = llvm.alloca %427 x i64 : (i64) -> !llvm.ptr
llvm.store %349, %428 : i64, !llvm.ptr
%429 = llvm.mlir.constant(1 : i64) : i64
%430 = llvm.alloca %429 x i64 : (i64) -> !llvm.ptr
llvm.store %137, %430 : i64, !llvm.ptr
%431 = arith.constant 1 : i32
%432 = llvm.load %160 : !llvm.ptr -> i64
%433 = arith.constant 1 : i32
%435 = arith.extsi %433 : i32 to i64
%434 = arith.addi %432, %435 : i64
%436 = arith.index_cast %431 : i32 to index
%437 = arith.index_cast %434 : i32 to index
%439 = arith.constant 1 : index
%440 = arith.constant -1 : index
%441 = arith.cmpi sle, %436, %437 : index
%438 = arith.select %441, %439, %440 : index
cf.br ^bb36(%436 : index)
^bb36(%442: index):
%443 = arith.cmpi slt, %442, %437 : index
%444 = arith.cmpi sgt, %442, %437 : index
%445 = arith.select %441, %443, %444 : i1
cf.cond_br %445, ^bb37(%442 : index), ^bb38(%442 : index)
^bb37(%446: index):
%447 = llvm.load %430 : !llvm.ptr -> i64
%448 = arith.remsi %447, %139 : i64
%449 = arith.extsi %448 : i64 to i128
%450 = llvm.load %430 : !llvm.ptr -> i64
%451 = arith.constant 1 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.subi %450, %453 : i64
%454 = arith.remsi %452, %139 : i64
%456 = arith.trunci %449 : i128 to i64
%455 = arith.muli %456, %454 : i64
%457 = arith.remsi %455, %139 : i64
%458 = llvm.mlir.constant(1 : i64) : i64
%459 = llvm.alloca %458 x i64 : (i64) -> !llvm.ptr
llvm.store %457, %459 : i64, !llvm.ptr
%460 = llvm.load %459 : !llvm.ptr -> i64
%461 = arith.extsi %460 : i64 to i128
%463 = llvm.load %428 : !llvm.ptr -> i64
%464 = arith.subi %463, %359 : i64
%465 = llvm.getelementptr %361[%464] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%462 = llvm.load %465 : !llvm.ptr -> i64
%467 = arith.trunci %461 : i128 to i64
%466 = arith.muli %467, %462 : i64
%468 = arith.remsi %466, %139 : i64
llvm.store %468, %459 : i64, !llvm.ptr
%469 = llvm.load %459 : !llvm.ptr -> i64
%470 = arith.extsi %469 : i64 to i128
%472 = llvm.load %428 : !llvm.ptr -> i64
%473 = arith.constant 1 : i32
%475 = arith.extsi %473 : i32 to i64
%474 = arith.subi %472, %475 : i64
%476 = arith.subi %474, %359 : i64
%477 = llvm.getelementptr %361[%476] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%471 = llvm.load %477 : !llvm.ptr -> i64
%479 = arith.trunci %470 : i128 to i64
%478 = arith.muli %479, %471 : i64
%480 = arith.remsi %478, %139 : i64
llvm.store %480, %459 : i64, !llvm.ptr
%481 = llvm.load %422 : !llvm.ptr -> i64
%482 = arith.extsi %481 : i64 to i128
%483 = llvm.load %459 : !llvm.ptr -> i64
%485 = arith.trunci %482 : i128 to i64
%484 = arith.muli %485, %483 : i64
%486 = arith.remsi %484, %139 : i64
llvm.store %486, %422 : i64, !llvm.ptr
%487 = llvm.load %428 : !llvm.ptr -> i64
%488 = arith.constant 2 : i32
%490 = arith.extsi %488 : i32 to i64
%489 = arith.subi %487, %490 : i64
llvm.store %489, %428 : i64, !llvm.ptr
%491 = llvm.load %430 : !llvm.ptr -> i64
%492 = arith.constant 2 : i32
%494 = arith.extsi %492 : i32 to i64
%493 = arith.subi %491, %494 : i64
llvm.store %493, %430 : i64, !llvm.ptr
%495 = arith.constant 2 : i32
%497 = arith.index_cast %446 : index to i32
%496 = arith.addi %497, %495 : i32
%498 = arith.constant 2 : i32
%499 = arith.divsi %496, %498 : i32
%500 = arith.extsi %499 : i32 to i64
%501 = arith.constant 1 : i32
%503 = arith.index_cast %446 : index to i32
%502 = arith.addi %503, %501 : i32
%504 = arith.constant 2 : i32
%505 = arith.divsi %502, %504 : i32
%506 = arith.extsi %505 : i32 to i64
%507 = arith.constant 0 : i32
%508 = arith.extsi %507 : i32 to i64
%509 = llvm.mlir.constant(1 : i64) : i64
%510 = llvm.alloca %509 x i64 : (i64) -> !llvm.ptr
llvm.store %508, %510 : i64, !llvm.ptr
%511 = llvm.load %131 : !llvm.ptr -> i64
%512 = arith.cmpi sle, %500, %511 : i64
%513 = scf.if %512 -> (i1) {
%514 = llvm.load %135 : !llvm.ptr -> i64
%515 = arith.cmpi sle, %506, %514 : i64
scf.yield %515 : i1
} else {
%516 = arith.constant false
scf.yield %516 : i1
}
cf.cond_br %513, ^bb39, ^bb40
^bb39:
%518 = arith.constant 1 : i32
%520 = arith.extsi %518 : i32 to i64
%519 = arith.subi %500, %520 : i64
%521 = llvm.getelementptr %225[%519] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%517 = llvm.load %521 : !llvm.ptr -> i64
%522 = arith.extsi %517 : i64 to i128
%524 = arith.constant 1 : i32
%526 = arith.extsi %524 : i32 to i64
%525 = arith.subi %506, %526 : i64
%527 = llvm.getelementptr %287[%525] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%523 = llvm.load %527 : !llvm.ptr -> i64
%529 = arith.trunci %522 : i128 to i64
%528 = arith.muli %529, %523 : i64
%530 = arith.remsi %528, %139 : i64
llvm.store %530, %510 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%531 = arith.constant 1 : i32
%533 = arith.index_cast %446 : index to i32
%532 = arith.addi %533, %531 : i32
%534 = arith.constant 2 : i32
%535 = arith.divsi %532, %534 : i32
%536 = arith.extsi %535 : i32 to i64
%537 = arith.constant 2 : i32
%539 = arith.index_cast %446 : index to i32
%538 = arith.addi %539, %537 : i32
%540 = arith.constant 2 : i32
%541 = arith.divsi %538, %540 : i32
%542 = arith.extsi %541 : i32 to i64
%543 = llvm.load %131 : !llvm.ptr -> i64
%544 = arith.cmpi sle, %536, %543 : i64
%545 = scf.if %544 -> (i1) {
%546 = llvm.load %135 : !llvm.ptr -> i64
%547 = arith.cmpi sle, %542, %546 : i64
scf.yield %547 : i1
} else {
%548 = arith.constant false
scf.yield %548 : i1
}
cf.cond_br %545, ^bb42, ^bb43
^bb42:
%549 = llvm.load %510 : !llvm.ptr -> i64
%551 = arith.constant 1 : i32
%553 = arith.extsi %551 : i32 to i64
%552 = arith.subi %536, %553 : i64
%554 = llvm.getelementptr %225[%552] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%550 = llvm.load %554 : !llvm.ptr -> i64
%555 = arith.extsi %550 : i64 to i128
%557 = arith.constant 1 : i32
%559 = arith.extsi %557 : i32 to i64
%558 = arith.subi %542, %559 : i64
%560 = llvm.getelementptr %287[%558] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%556 = llvm.load %560 : !llvm.ptr -> i64
%562 = arith.trunci %555 : i128 to i64
%561 = arith.muli %562, %556 : i64
%563 = arith.remsi %561, %139 : i64
%564 = arith.addi %549, %563 : i64
%565 = arith.remsi %564, %139 : i64
llvm.store %565, %510 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%566 = llvm.load %426 : !llvm.ptr -> i64
%567 = llvm.load %510 : !llvm.ptr -> i64
%568 = arith.extsi %567 : i64 to i128
%569 = llvm.load %422 : !llvm.ptr -> i64
%571 = arith.trunci %568 : i128 to i64
%570 = arith.muli %571, %569 : i64
%572 = arith.remsi %570, %139 : i64
%573 = arith.addi %566, %572 : i64
%574 = arith.remsi %573, %139 : i64
llvm.store %574, %426 : i64, !llvm.ptr
%575 = arith.addi %446, %438 : index
cf.br ^bb36(%575 : index)
^bb38(%576: index):
%577 = llvm.mlir.addressof @str_0 : !llvm.ptr
%578 = llvm.load %426 : !llvm.ptr -> i64
%579 = llvm.call @printf(%577, %578) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%178) : (!llvm.ptr) -> ()
func.call @free(%225) : (!llvm.ptr) -> ()
func.call @free(%287) : (!llvm.ptr) -> ()
func.call @free(%361) : (!llvm.ptr) -> ()
%584 = arith.constant 0 : i32
func.return %584 : i32
}
}