← All problems Problem 797
Cyclogenic Polynomials: Q_{10^7}(2) mod 1e9+7. Linear sieve + cyclotomic polynomial at 2 + Mobius inversion.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(n log log n)Space complexity O(n^2)O(n)Approach Flow solution Mobius sieve Verdict Suboptimal
Flow source
# Project Euler 797
# Cyclogenic Polynomials: Q_{10^7}(2) mod 1e9+7.
# Linear sieve + cyclotomic polynomial at 2 + Mobius inversion.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
const N: i64 = 10000000
function mod_pow(a: i64, e: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = a % MOD
let mut ee: i64 = e
while ee > 0 {
if (ee & 1) != 0 {
r = r * b % MOD
}
b = b * b % MOD
ee = ee >> 1
}
return r
}
function main() -> i32 {
# Linear sieve for spf and mu
let spf: ptr<i32> = calloc(N + 1, 4) as ptr<i32>
let mu: ptr<i8> = calloc(N + 1, 1) as ptr<i8>
let primes: ptr<i32> = calloc(N / 10 + 1000, 4) as ptr<i32>
let mut pc: i64 = 0
spf[1] = 1
mu[1] = 1
for i in 2..(N + 1) {
if spf[i] == 0 {
spf[i] = i as i32
primes[pc] = i as i32
pc = pc + 1
mu[i] = -1
}
let mut j: i64 = 0
while j < pc {
let p: i64 = primes[j] as i64
let ip: i64 = i * p
if ip > N { break }
spf[ip] = p as i32
if i % p == 0 {
mu[ip] = 0
break
}
mu[ip] = -mu[i]
j = j + 1
}
}
# Build b_arr[k] = 2^k - 1 mod MOD and invb[k] = inverse
let b_arr: ptr<i64> = calloc(N + 1, 8) as ptr<i64>
let invb: ptr<i64> = calloc(N + 1, 8) as ptr<i64>
let mut pow2: i64 = 1
for k in 1..(N + 1) {
pow2 = pow2 * 2 % MOD
b_arr[k] = pow2 - 1
}
# Batch inversion using prefix products
invb[0] = 1
let mut acc: i64 = 1
for k in 1..(N + 1) {
acc = acc * b_arr[k] % MOD
invb[k] = acc
}
let mut inv_total: i64 = mod_pow(acc, MOD - 2)
let mut k: i64 = N
while k >= 1 {
let prev_prefix: i64 = invb[k - 1]
invb[k] = inv_total * prev_prefix % MOD
inv_total = inv_total * b_arr[k] % MOD
k = k - 1
}
invb[0] = 0
# Build T[k] = product_{d|k} (1 + Phi_d(2)), then prefix sums
let T: ptr<i64> = calloc(N + 1, 8) as ptr<i64>
for i in 0..(N + 1) {
T[i] = 1
}
T[0] = 0
# Working arrays for cyclotomic computation (reused)
let pp: ptr<i32> = calloc(16, 4) as ptr<i32>
let prod: ptr<i64> = calloc(256, 8) as ptr<i64>
let par: ptr<i32> = calloc(256, 4) as ptr<i32>
for d in 1..(N + 1) {
let mut phi_d: i64 = 0
if d == 1 {
phi_d = 1
} else {
# Extract distinct primes of d
let mut m: i64 = d
let mut npc: i64 = 0
while m > 1 {
let p: i64 = spf[m] as i64
pp[npc] = p as i32
npc = npc + 1
while m % p == 0 {
m = m / p
}
}
# Enumerate squarefree divisors with parity
let mut cnt: i64 = 1
prod[0] = 1
par[0] = 0
for i in 0..npc {
let L: i64 = cnt
for j in 0..L {
prod[cnt] = prod[j] * (pp[i] as i64)
par[cnt] = par[j] ^ 1
cnt = cnt + 1
}
}
let mut res: i64 = 1
for i in 0..cnt {
let idx: i64 = d / prod[i]
if par[i] == 0 {
res = res * b_arr[idx] % MOD
} else {
res = res * invb[idx] % MOD
}
}
phi_d = res
}
let mut fd: i64 = phi_d + 1
if fd >= MOD { fd = fd - MOD }
let mut mm: i64 = d
while mm <= N {
T[mm] = T[mm] * fd % MOD
mm = mm + d
}
}
free(pp)
free(prod)
free(par)
free(b_arr)
free(invb)
free(spf)
# Prefix sum T in-place
let mut run: i64 = 0
for i in 1..(N + 1) {
run = run + T[i]
if run >= MOD { run = run - MOD }
T[i] = run
}
# Prefix sums of mu (Mertens function)
let prefix_mu: ptr<i32> = calloc(N + 1, 4) as ptr<i32>
let mut run_mu: i32 = 0
for i in 1..(N + 1) {
run_mu = run_mu + (mu[i] as i32)
prefix_mu[i] = run_mu
}
# Q_n = sum_{d<=n} mu(d) * T_prefix[n/d], grouped by floor division
let mut ans: i64 = 0
let mut l: i64 = 1
while l <= N {
let t: i64 = N / l
let r: i64 = N / t
let sum_mu: i64 = (prefix_mu[r] - prefix_mu[l - 1]) as i64
let term: i64 = (sum_mu % MOD) * T[t]
ans = (ans + term) % MOD
l = r + 1
}
ans = ans % MOD
if ans < 0 { ans = ans + MOD }
free(prefix_mu)
free(mu)
free(primes)
free(T)
printf("%lld\n", ans)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t mod_pow_i64_i64(int64_t a, int64_t e);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t N = 10000000;
int64_t mod_pow_i64_i64(int64_t a, int64_t e) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((a), (MOD));
int64_t ee = e;
while (ee > 0) {
if ((ee & 1) != 0) {
r = FLOW_CHECKED_MOD(((r * b)), (MOD));
}
b = FLOW_CHECKED_MOD(((b * b)), (MOD));
ee = FLOW_CHECKED_SHR((ee), (1));
}
return r;
}
int32_t main(void) {
int32_t* spf = (int32_t*)(((int32_t*)(calloc((N + 1), 4))));
int8_t* mu = (int8_t*)(((int8_t*)(calloc((N + 1), 1))));
int32_t* primes = (int32_t*)(((int32_t*)(calloc((FLOW_CHECKED_DIV((N), (10)) + 1000), 4))));
int64_t pc = 0;
spf[1] = 1;
mu[1] = 1;
int32_t __flow_step_1 = 1;
for (int32_t i = 2; (2 <= (N + 1)) ? i < (N + 1) : i > (N + 1); i += (2 <= (N + 1)) ? 1 : -1) {
if (spf[i] == 0) {
spf[i] = ((int32_t)(i));
primes[pc] = ((int32_t)(i));
pc = (pc + 1);
mu[i] = (-1);
}
int64_t j = 0;
while (j < pc) {
int64_t p = ((int64_t)(primes[j]));
int64_t ip = (i * p);
if (ip > N) {
break;
}
spf[ip] = ((int32_t)(p));
if (FLOW_CHECKED_MOD((i), (p)) == 0) {
mu[ip] = 0;
break;
}
mu[ip] = (-mu[i]);
j = (j + 1);
}
}
int64_t* b_arr = (int64_t*)(((int64_t*)(calloc((N + 1), 8))));
int64_t* invb = (int64_t*)(((int64_t*)(calloc((N + 1), 8))));
int64_t pow2 = 1;
int32_t __flow_step_2 = 1;
for (int32_t k = 1; (1 <= (N + 1)) ? k < (N + 1) : k > (N + 1); k += (1 <= (N + 1)) ? 1 : -1) {
pow2 = FLOW_CHECKED_MOD(((pow2 * 2)), (MOD));
b_arr[k] = (pow2 - 1);
}
invb[0] = 1;
int64_t acc = 1;
int32_t __flow_step_3 = 1;
for (int32_t k = 1; (1 <= (N + 1)) ? k < (N + 1) : k > (N + 1); k += (1 <= (N + 1)) ? 1 : -1) {
acc = FLOW_CHECKED_MOD(((acc * b_arr[k])), (MOD));
invb[k] = acc;
}
int64_t inv_total = mod_pow_i64_i64(acc, (MOD - 2));
int64_t k = N;
while (k >= 1) {
int64_t prev_prefix = invb[(k - 1)];
invb[k] = FLOW_CHECKED_MOD(((inv_total * prev_prefix)), (MOD));
inv_total = FLOW_CHECKED_MOD(((inv_total * b_arr[k])), (MOD));
k = (k - 1);
}
invb[0] = 0;
int64_t* T = (int64_t*)(((int64_t*)(calloc((N + 1), 8))));
int32_t __flow_step_4 = 1;
for (int32_t i = 0; (0 <= (N + 1)) ? i < (N + 1) : i > (N + 1); i += (0 <= (N + 1)) ? 1 : -1) {
T[i] = 1;
}
T[0] = 0;
int32_t* pp = (int32_t*)(((int32_t*)(calloc(16, 4))));
int64_t* prod = (int64_t*)(((int64_t*)(calloc(256, 8))));
int32_t* par = (int32_t*)(((int32_t*)(calloc(256, 4))));
int32_t __flow_step_5 = 1;
for (int32_t d = 1; (1 <= (N + 1)) ? d < (N + 1) : d > (N + 1); d += (1 <= (N + 1)) ? 1 : -1) {
int64_t phi_d = 0;
if (d == 1) {
phi_d = 1;
} else {
int64_t m = d;
int64_t npc = 0;
while (m > 1) {
int64_t p = ((int64_t)(spf[m]));
pp[npc] = ((int32_t)(p));
npc = (npc + 1);
while (FLOW_CHECKED_MOD((m), (p)) == 0) {
m = FLOW_CHECKED_DIV((m), (p));
}
}
int64_t cnt = 1;
prod[0] = 1;
par[0] = 0;
int32_t __flow_step_6 = 1;
for (int32_t i = 0; (0 <= npc) ? i < npc : i > npc; i += (0 <= npc) ? 1 : -1) {
int64_t L = cnt;
int32_t __flow_step_7 = 1;
for (int32_t j = 0; (0 <= L) ? j < L : j > L; j += (0 <= L) ? 1 : -1) {
prod[cnt] = (prod[j] * ((int64_t)(pp[i])));
par[cnt] = (par[j] ^ 1);
cnt = (cnt + 1);
}
}
int64_t res = 1;
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= cnt) ? i < cnt : i > cnt; i += (0 <= cnt) ? 1 : -1) {
int64_t idx = FLOW_CHECKED_DIV((d), (prod[i]));
if (par[i] == 0) {
res = FLOW_CHECKED_MOD(((res * b_arr[idx])), (MOD));
} else {
res = FLOW_CHECKED_MOD(((res * invb[idx])), (MOD));
}
}
phi_d = res;
}
int64_t fd = (phi_d + 1);
if (fd >= MOD) {
fd = (fd - MOD);
}
int64_t mm = d;
while (mm <= N) {
T[mm] = FLOW_CHECKED_MOD(((T[mm] * fd)), (MOD));
mm = (mm + d);
}
}
free(pp);
free(prod);
free(par);
free(b_arr);
free(invb);
free(spf);
int64_t run = 0;
int32_t __flow_step_9 = 1;
for (int32_t i = 1; (1 <= (N + 1)) ? i < (N + 1) : i > (N + 1); i += (1 <= (N + 1)) ? 1 : -1) {
run = (run + T[i]);
if (run >= MOD) {
run = (run - MOD);
}
T[i] = run;
}
int32_t* prefix_mu = (int32_t*)(((int32_t*)(calloc((N + 1), 4))));
int32_t run_mu = 0;
int32_t __flow_step_10 = 1;
for (int32_t i = 1; (1 <= (N + 1)) ? i < (N + 1) : i > (N + 1); i += (1 <= (N + 1)) ? 1 : -1) {
run_mu = (run_mu + ((int32_t)(mu[i])));
prefix_mu[i] = run_mu;
}
int64_t ans = 0;
int64_t l = 1;
while (l <= N) {
int64_t t = FLOW_CHECKED_DIV((N), (l));
int64_t r = FLOW_CHECKED_DIV((N), (t));
int64_t sum_mu = ((int64_t)((prefix_mu[r] - prefix_mu[(l - 1)])));
int64_t term = (FLOW_CHECKED_MOD((sum_mu), (MOD)) * T[t]);
ans = FLOW_CHECKED_MOD(((ans + term)), (MOD));
l = (r + 1);
}
ans = FLOW_CHECKED_MOD((ans), (MOD));
if (ans < 0) {
ans = (ans + MOD);
}
free(prefix_mu);
free(mu);
free(primes);
free(T);
printf("%lld\n", ans);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Constant: N
llvm.mlir.global internal constant @N(10000000 : i64) : i64
func.func @mod_pow(%arg0: i64, %arg1: 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 = llvm.mlir.addressof @MOD : !llvm.ptr
%5 = llvm.load %4 : !llvm.ptr -> i64
%6 = arith.remsi %arg0, %5 : i64
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %6, %8 : i64, !llvm.ptr
%9 = llvm.mlir.constant(1 : i64) : i64
%10 = llvm.alloca %9 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %10 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%11 = llvm.load %10 : !llvm.ptr -> i64
%12 = arith.constant 0 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.cmpi sgt, %11, %14 : i64
cf.cond_br %13, ^bb1, ^bb2
^bb1:
%15 = llvm.load %10 : !llvm.ptr -> i64
%16 = arith.constant 1 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.andi %15, %18 : i64
%19 = arith.constant 0 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.cmpi ne, %17, %21 : i64
cf.cond_br %20, ^bb3, ^bb4
^bb3:
%22 = llvm.load %3 : !llvm.ptr -> i64
%23 = llvm.load %8 : !llvm.ptr -> i64
%24 = arith.muli %22, %23 : i64
%25 = llvm.mlir.addressof @MOD : !llvm.ptr
%26 = llvm.load %25 : !llvm.ptr -> i64
%27 = arith.remsi %24, %26 : i64
llvm.store %27, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%28 = llvm.load %8 : !llvm.ptr -> i64
%29 = llvm.load %8 : !llvm.ptr -> i64
%30 = arith.muli %28, %29 : i64
%31 = llvm.mlir.addressof @MOD : !llvm.ptr
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.remsi %30, %32 : i64
llvm.store %33, %8 : i64, !llvm.ptr
%34 = llvm.load %10 : !llvm.ptr -> i64
%35 = arith.constant 1 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.shrsi %34, %37 : i64
llvm.store %36, %10 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%38 = llvm.load %3 : !llvm.ptr -> i64
func.return %38 : i64
}
func.func @main() -> i32 {
%40 = llvm.mlir.addressof @N : !llvm.ptr
%41 = llvm.load %40 : !llvm.ptr -> i64
%42 = arith.constant 1 : i32
%44 = arith.extsi %42 : i32 to i64
%43 = arith.addi %41, %44 : i64
%45 = arith.constant 4 : i32
%46 = arith.extsi %45 : i32 to i64
%39 = func.call @calloc(%43, %46) : (i64, i64) -> !llvm.ptr
%48 = llvm.mlir.addressof @N : !llvm.ptr
%49 = llvm.load %48 : !llvm.ptr -> i64
%50 = arith.constant 1 : i32
%52 = arith.extsi %50 : i32 to i64
%51 = arith.addi %49, %52 : i64
%53 = arith.constant 1 : i32
%54 = arith.extsi %53 : i32 to i64
%47 = func.call @calloc(%51, %54) : (i64, i64) -> !llvm.ptr
%56 = llvm.mlir.addressof @N : !llvm.ptr
%57 = llvm.load %56 : !llvm.ptr -> i64
%58 = arith.constant 10 : i32
%60 = arith.extsi %58 : i32 to i64
%59 = arith.divsi %57, %60 : i64
%61 = arith.constant 1000 : i32
%63 = arith.extsi %61 : i32 to i64
%62 = arith.addi %59, %63 : i64
%64 = arith.constant 4 : i32
%65 = arith.extsi %64 : i32 to i64
%55 = func.call @calloc(%62, %65) : (i64, i64) -> !llvm.ptr
%66 = arith.constant 0 : i32
%67 = arith.extsi %66 : i32 to i64
%68 = llvm.mlir.constant(1 : i64) : i64
%69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
llvm.store %67, %69 : i64, !llvm.ptr
%70 = arith.constant 1 : i32
%71 = arith.constant 1 : i32
%72 = arith.extsi %71 : i32 to i64
%73 = llvm.getelementptr %39[%72] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %70, %73 : i32, !llvm.ptr
%74 = arith.constant 1 : i32
%75 = arith.constant 1 : i32
%76 = arith.trunci %74 : i32 to i8
%77 = arith.extsi %75 : i32 to i64
%78 = llvm.getelementptr %47[%77] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %76, %78 : i8, !llvm.ptr
%79 = arith.constant 2 : i32
%80 = llvm.mlir.addressof @N : !llvm.ptr
%81 = llvm.load %80 : !llvm.ptr -> i64
%82 = arith.constant 1 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.addi %81, %84 : i64
%85 = arith.index_cast %79 : i32 to index
%86 = arith.index_cast %83 : i32 to index
%88 = arith.constant 1 : index
%89 = arith.constant -1 : index
%90 = arith.cmpi sle, %85, %86 : index
%87 = arith.select %90, %88, %89 : index
cf.br ^bb6(%85 : index)
^bb6(%91: index):
%92 = arith.cmpi slt, %91, %86 : index
%93 = arith.cmpi sgt, %91, %86 : index
%94 = arith.select %90, %92, %93 : i1
cf.cond_br %94, ^bb7(%91 : index), ^bb8(%91 : index)
^bb7(%95: index):
%97 = arith.index_cast %95 : index to i64
%98 = llvm.getelementptr %39[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%96 = llvm.load %98 : !llvm.ptr -> i32
%99 = arith.constant 0 : i32
%100 = arith.cmpi eq, %96, %99 : i32
cf.cond_br %100, ^bb9, ^bb10
^bb9:
%101 = arith.index_cast %95 : index to i32
%102 = arith.index_cast %95 : index to i64
%103 = llvm.getelementptr %39[%102] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %101, %103 : i32, !llvm.ptr
%104 = arith.index_cast %95 : index to i32
%105 = llvm.load %69 : !llvm.ptr -> i64
%106 = llvm.getelementptr %55[%105] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %104, %106 : i32, !llvm.ptr
%107 = llvm.load %69 : !llvm.ptr -> i64
%108 = arith.constant 1 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.addi %107, %110 : i64
llvm.store %109, %69 : i64, !llvm.ptr
%111 = arith.constant 1 : i32
%113 = arith.constant 0 : i32
%112 = arith.subi %113, %111 : i32
%114 = arith.trunci %112 : i32 to i8
%115 = arith.index_cast %95 : index to i64
%116 = llvm.getelementptr %47[%115] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %114, %116 : i8, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%117 = arith.constant 0 : i32
%118 = arith.extsi %117 : i32 to i64
%119 = llvm.mlir.constant(1 : i64) : i64
%120 = llvm.alloca %119 x i64 : (i64) -> !llvm.ptr
llvm.store %118, %120 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%121 = llvm.load %120 : !llvm.ptr -> i64
%122 = llvm.load %69 : !llvm.ptr -> i64
%123 = arith.cmpi slt, %121, %122 : i64
cf.cond_br %123, ^bb13, ^bb14
^bb13:
%125 = llvm.load %120 : !llvm.ptr -> i64
%126 = llvm.getelementptr %55[%125] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%124 = llvm.load %126 : !llvm.ptr -> i32
%127 = arith.extsi %124 : i32 to i64
%129 = arith.index_cast %95 : index to i32
%130 = arith.trunci %127 : i64 to i32
%128 = arith.muli %129, %130 : i32
%131 = arith.extsi %128 : i32 to i64
%132 = llvm.mlir.addressof @N : !llvm.ptr
%133 = llvm.load %132 : !llvm.ptr -> i64
%134 = arith.cmpi sgt, %131, %133 : i64
cf.cond_br %134, ^bb15, ^bb16
^bb15:
cf.br ^bb14
^bb16:
cf.br ^bb17
^bb17:
%135 = arith.trunci %127 : i64 to i32
%136 = llvm.getelementptr %39[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %135, %136 : i32, !llvm.ptr
%138 = arith.index_cast %95 : index to i32
%139 = arith.trunci %127 : i64 to i32
%137 = arith.remsi %138, %139 : i32
%140 = arith.constant 0 : i32
%141 = arith.cmpi eq, %137, %140 : i32
cf.cond_br %141, ^bb18, ^bb19
^bb18:
%142 = arith.constant 0 : i32
%143 = arith.trunci %142 : i32 to i8
%144 = llvm.getelementptr %47[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %143, %144 : i8, !llvm.ptr
cf.br ^bb14
^bb19:
cf.br ^bb20
^bb20:
%146 = arith.index_cast %95 : index to i64
%147 = llvm.getelementptr %47[%146] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%145 = llvm.load %147 : !llvm.ptr -> i8
%149 = arith.constant 0 : i8
%148 = arith.subi %149, %145 : i8
%150 = llvm.getelementptr %47[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %148, %150 : i8, !llvm.ptr
%151 = llvm.load %120 : !llvm.ptr -> i64
%152 = arith.constant 1 : i32
%154 = arith.extsi %152 : i32 to i64
%153 = arith.addi %151, %154 : i64
llvm.store %153, %120 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%155 = arith.addi %95, %87 : index
cf.br ^bb6(%155 : index)
^bb8(%156: index):
%158 = llvm.mlir.addressof @N : !llvm.ptr
%159 = llvm.load %158 : !llvm.ptr -> i64
%160 = arith.constant 1 : i32
%162 = arith.extsi %160 : i32 to i64
%161 = arith.addi %159, %162 : i64
%163 = arith.constant 8 : i32
%164 = arith.extsi %163 : i32 to i64
%157 = func.call @calloc(%161, %164) : (i64, i64) -> !llvm.ptr
%166 = llvm.mlir.addressof @N : !llvm.ptr
%167 = llvm.load %166 : !llvm.ptr -> i64
%168 = arith.constant 1 : i32
%170 = arith.extsi %168 : i32 to i64
%169 = arith.addi %167, %170 : i64
%171 = arith.constant 8 : i32
%172 = arith.extsi %171 : i32 to i64
%165 = func.call @calloc(%169, %172) : (i64, i64) -> !llvm.ptr
%173 = arith.constant 1 : i32
%174 = arith.extsi %173 : i32 to i64
%175 = llvm.mlir.constant(1 : i64) : i64
%176 = llvm.alloca %175 x i64 : (i64) -> !llvm.ptr
llvm.store %174, %176 : i64, !llvm.ptr
%177 = arith.constant 1 : i32
%178 = llvm.mlir.addressof @N : !llvm.ptr
%179 = llvm.load %178 : !llvm.ptr -> i64
%180 = arith.constant 1 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.addi %179, %182 : i64
%183 = arith.index_cast %177 : i32 to index
%184 = arith.index_cast %181 : i32 to index
%186 = arith.constant 1 : index
%187 = arith.constant -1 : index
%188 = arith.cmpi sle, %183, %184 : index
%185 = arith.select %188, %186, %187 : index
cf.br ^bb21(%183 : index)
^bb21(%189: index):
%190 = arith.cmpi slt, %189, %184 : index
%191 = arith.cmpi sgt, %189, %184 : index
%192 = arith.select %188, %190, %191 : i1
cf.cond_br %192, ^bb22(%189 : index), ^bb23(%189 : index)
^bb22(%193: index):
%194 = llvm.load %176 : !llvm.ptr -> i64
%195 = arith.constant 2 : i32
%197 = arith.extsi %195 : i32 to i64
%196 = arith.muli %194, %197 : i64
%198 = llvm.mlir.addressof @MOD : !llvm.ptr
%199 = llvm.load %198 : !llvm.ptr -> i64
%200 = arith.remsi %196, %199 : i64
llvm.store %200, %176 : i64, !llvm.ptr
%201 = llvm.load %176 : !llvm.ptr -> i64
%202 = arith.constant 1 : i32
%204 = arith.extsi %202 : i32 to i64
%203 = arith.subi %201, %204 : i64
%205 = arith.index_cast %193 : index to i64
%206 = llvm.getelementptr %157[%205] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %203, %206 : i64, !llvm.ptr
%207 = arith.addi %193, %185 : index
cf.br ^bb21(%207 : index)
^bb23(%208: index):
%209 = arith.constant 1 : i32
%210 = arith.constant 0 : i32
%211 = arith.extsi %209 : i32 to i64
%212 = arith.extsi %210 : i32 to i64
%213 = llvm.getelementptr %165[%212] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %211, %213 : i64, !llvm.ptr
%214 = arith.constant 1 : 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
%218 = arith.constant 1 : i32
%219 = llvm.mlir.addressof @N : !llvm.ptr
%220 = llvm.load %219 : !llvm.ptr -> i64
%221 = arith.constant 1 : i32
%223 = arith.extsi %221 : i32 to i64
%222 = arith.addi %220, %223 : i64
%224 = arith.index_cast %218 : i32 to index
%225 = arith.index_cast %222 : i32 to index
%227 = arith.constant 1 : index
%228 = arith.constant -1 : index
%229 = arith.cmpi sle, %224, %225 : index
%226 = arith.select %229, %227, %228 : index
cf.br ^bb24(%224 : index)
^bb24(%230: index):
%231 = arith.cmpi slt, %230, %225 : index
%232 = arith.cmpi sgt, %230, %225 : index
%233 = arith.select %229, %231, %232 : i1
cf.cond_br %233, ^bb25(%230 : index), ^bb26(%230 : index)
^bb25(%234: index):
%235 = llvm.load %217 : !llvm.ptr -> i64
%237 = arith.index_cast %234 : index to i64
%238 = llvm.getelementptr %157[%237] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%236 = llvm.load %238 : !llvm.ptr -> i64
%239 = arith.muli %235, %236 : i64
%240 = llvm.mlir.addressof @MOD : !llvm.ptr
%241 = llvm.load %240 : !llvm.ptr -> i64
%242 = arith.remsi %239, %241 : i64
llvm.store %242, %217 : i64, !llvm.ptr
%243 = llvm.load %217 : !llvm.ptr -> i64
%244 = arith.index_cast %234 : index to i64
%245 = llvm.getelementptr %165[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %243, %245 : i64, !llvm.ptr
%246 = arith.addi %234, %226 : index
cf.br ^bb24(%246 : index)
^bb26(%247: index):
%249 = llvm.load %217 : !llvm.ptr -> i64
%250 = llvm.mlir.addressof @MOD : !llvm.ptr
%251 = llvm.load %250 : !llvm.ptr -> i64
%252 = arith.constant 2 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.subi %251, %254 : i64
%248 = func.call @mod_pow(%249, %253) : (i64, i64) -> i64
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i64 : (i64) -> !llvm.ptr
llvm.store %248, %256 : i64, !llvm.ptr
%257 = llvm.mlir.addressof @N : !llvm.ptr
%258 = llvm.load %257 : !llvm.ptr -> i64
%259 = llvm.mlir.constant(1 : i64) : i64
%260 = llvm.alloca %259 x i64 : (i64) -> !llvm.ptr
llvm.store %258, %260 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%261 = llvm.load %260 : !llvm.ptr -> i64
%262 = arith.constant 1 : i32
%264 = arith.extsi %262 : i32 to i64
%263 = arith.cmpi sge, %261, %264 : i64
cf.cond_br %263, ^bb28, ^bb29
^bb28:
%266 = llvm.load %260 : !llvm.ptr -> i64
%267 = arith.constant 1 : i32
%269 = arith.extsi %267 : i32 to i64
%268 = arith.subi %266, %269 : i64
%270 = llvm.getelementptr %165[%268] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%265 = llvm.load %270 : !llvm.ptr -> i64
%271 = llvm.load %256 : !llvm.ptr -> i64
%272 = arith.muli %271, %265 : i64
%273 = llvm.mlir.addressof @MOD : !llvm.ptr
%274 = llvm.load %273 : !llvm.ptr -> i64
%275 = arith.remsi %272, %274 : i64
%276 = llvm.load %260 : !llvm.ptr -> i64
%277 = llvm.getelementptr %165[%276] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %275, %277 : i64, !llvm.ptr
%278 = llvm.load %256 : !llvm.ptr -> i64
%280 = llvm.load %260 : !llvm.ptr -> i64
%281 = llvm.getelementptr %157[%280] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%279 = llvm.load %281 : !llvm.ptr -> i64
%282 = arith.muli %278, %279 : i64
%283 = llvm.mlir.addressof @MOD : !llvm.ptr
%284 = llvm.load %283 : !llvm.ptr -> i64
%285 = arith.remsi %282, %284 : i64
llvm.store %285, %256 : i64, !llvm.ptr
%286 = llvm.load %260 : !llvm.ptr -> i64
%287 = arith.constant 1 : i32
%289 = arith.extsi %287 : i32 to i64
%288 = arith.subi %286, %289 : i64
llvm.store %288, %260 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%290 = arith.constant 0 : i32
%291 = arith.constant 0 : i32
%292 = arith.extsi %290 : i32 to i64
%293 = arith.extsi %291 : i32 to i64
%294 = llvm.getelementptr %165[%293] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %292, %294 : i64, !llvm.ptr
%296 = llvm.mlir.addressof @N : !llvm.ptr
%297 = llvm.load %296 : !llvm.ptr -> i64
%298 = arith.constant 1 : i32
%300 = arith.extsi %298 : i32 to i64
%299 = arith.addi %297, %300 : i64
%301 = arith.constant 8 : i32
%302 = arith.extsi %301 : i32 to i64
%295 = func.call @calloc(%299, %302) : (i64, i64) -> !llvm.ptr
%303 = arith.constant 0 : i32
%304 = llvm.mlir.addressof @N : !llvm.ptr
%305 = llvm.load %304 : !llvm.ptr -> i64
%306 = arith.constant 1 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.addi %305, %308 : i64
%309 = arith.index_cast %303 : i32 to index
%310 = arith.index_cast %307 : i32 to index
%312 = arith.constant 1 : index
%313 = arith.constant -1 : index
%314 = arith.cmpi sle, %309, %310 : index
%311 = arith.select %314, %312, %313 : index
cf.br ^bb30(%309 : index)
^bb30(%315: index):
%316 = arith.cmpi slt, %315, %310 : index
%317 = arith.cmpi sgt, %315, %310 : index
%318 = arith.select %314, %316, %317 : i1
cf.cond_br %318, ^bb31(%315 : index), ^bb32(%315 : index)
^bb31(%319: index):
%320 = arith.constant 1 : i32
%321 = arith.extsi %320 : i32 to i64
%322 = arith.index_cast %319 : index to i64
%323 = llvm.getelementptr %295[%322] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %321, %323 : i64, !llvm.ptr
%324 = arith.addi %319, %311 : index
cf.br ^bb30(%324 : index)
^bb32(%325: index):
%326 = arith.constant 0 : i32
%327 = arith.constant 0 : i32
%328 = arith.extsi %326 : i32 to i64
%329 = arith.extsi %327 : i32 to i64
%330 = llvm.getelementptr %295[%329] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %328, %330 : i64, !llvm.ptr
%332 = arith.constant 16 : i32
%333 = arith.constant 4 : i32
%334 = arith.extsi %332 : i32 to i64
%335 = arith.extsi %333 : i32 to i64
%331 = func.call @calloc(%334, %335) : (i64, i64) -> !llvm.ptr
%337 = arith.constant 256 : i32
%338 = arith.constant 8 : i32
%339 = arith.extsi %337 : i32 to i64
%340 = arith.extsi %338 : i32 to i64
%336 = func.call @calloc(%339, %340) : (i64, i64) -> !llvm.ptr
%342 = arith.constant 256 : i32
%343 = arith.constant 4 : i32
%344 = arith.extsi %342 : i32 to i64
%345 = arith.extsi %343 : i32 to i64
%341 = func.call @calloc(%344, %345) : (i64, i64) -> !llvm.ptr
%346 = arith.constant 1 : i32
%347 = llvm.mlir.addressof @N : !llvm.ptr
%348 = llvm.load %347 : !llvm.ptr -> i64
%349 = arith.constant 1 : i32
%351 = arith.extsi %349 : i32 to i64
%350 = arith.addi %348, %351 : i64
%352 = arith.index_cast %346 : i32 to index
%353 = arith.index_cast %350 : i32 to index
%355 = arith.constant 1 : index
%356 = arith.constant -1 : index
%357 = arith.cmpi sle, %352, %353 : index
%354 = arith.select %357, %355, %356 : index
cf.br ^bb33(%352 : index)
^bb33(%358: index):
%359 = arith.cmpi slt, %358, %353 : index
%360 = arith.cmpi sgt, %358, %353 : index
%361 = arith.select %357, %359, %360 : i1
cf.cond_br %361, ^bb34(%358 : index), ^bb35(%358 : index)
^bb34(%362: index):
%363 = arith.constant 0 : i32
%364 = arith.extsi %363 : i32 to i64
%365 = llvm.mlir.constant(1 : i64) : i64
%366 = llvm.alloca %365 x i64 : (i64) -> !llvm.ptr
llvm.store %364, %366 : i64, !llvm.ptr
%367 = arith.constant 1 : i32
%369 = arith.index_cast %362 : index to i32
%368 = arith.cmpi eq, %369, %367 : i32
cf.cond_br %368, ^bb36, ^bb37
^bb36:
%370 = arith.constant 1 : i32
%371 = arith.extsi %370 : i32 to i64
llvm.store %371, %366 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
%372 = arith.index_cast %362 : index to i64
%373 = llvm.mlir.constant(1 : i64) : i64
%374 = llvm.alloca %373 x i64 : (i64) -> !llvm.ptr
llvm.store %372, %374 : i64, !llvm.ptr
%375 = arith.constant 0 : i32
%376 = arith.extsi %375 : i32 to i64
%377 = llvm.mlir.constant(1 : i64) : i64
%378 = llvm.alloca %377 x i64 : (i64) -> !llvm.ptr
llvm.store %376, %378 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%379 = llvm.load %374 : !llvm.ptr -> i64
%380 = arith.constant 1 : i32
%382 = arith.extsi %380 : i32 to i64
%381 = arith.cmpi sgt, %379, %382 : i64
cf.cond_br %381, ^bb40, ^bb41
^bb40:
%384 = llvm.load %374 : !llvm.ptr -> i64
%385 = llvm.getelementptr %39[%384] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%383 = llvm.load %385 : !llvm.ptr -> i32
%386 = arith.extsi %383 : i32 to i64
%387 = arith.trunci %386 : i64 to i32
%388 = llvm.load %378 : !llvm.ptr -> i64
%389 = llvm.getelementptr %331[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %387, %389 : i32, !llvm.ptr
%390 = llvm.load %378 : !llvm.ptr -> i64
%391 = arith.constant 1 : i32
%393 = arith.extsi %391 : i32 to i64
%392 = arith.addi %390, %393 : i64
llvm.store %392, %378 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%394 = llvm.load %374 : !llvm.ptr -> i64
%395 = arith.remsi %394, %386 : i64
%396 = arith.constant 0 : i32
%398 = arith.extsi %396 : i32 to i64
%397 = arith.cmpi eq, %395, %398 : i64
cf.cond_br %397, ^bb43, ^bb44
^bb43:
%399 = llvm.load %374 : !llvm.ptr -> i64
%400 = arith.divsi %399, %386 : i64
llvm.store %400, %374 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
cf.br ^bb39
^bb41:
%401 = arith.constant 1 : i32
%402 = arith.extsi %401 : i32 to i64
%403 = llvm.mlir.constant(1 : i64) : i64
%404 = llvm.alloca %403 x i64 : (i64) -> !llvm.ptr
llvm.store %402, %404 : i64, !llvm.ptr
%405 = arith.constant 1 : i32
%406 = arith.constant 0 : i32
%407 = arith.extsi %405 : i32 to i64
%408 = arith.extsi %406 : i32 to i64
%409 = llvm.getelementptr %336[%408] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %407, %409 : i64, !llvm.ptr
%410 = arith.constant 0 : i32
%411 = arith.constant 0 : i32
%412 = arith.extsi %411 : i32 to i64
%413 = llvm.getelementptr %341[%412] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %410, %413 : i32, !llvm.ptr
%414 = arith.constant 0 : i32
%415 = llvm.load %378 : !llvm.ptr -> i64
%416 = arith.index_cast %414 : i32 to index
%417 = arith.index_cast %415 : i32 to index
%419 = arith.constant 1 : index
%420 = arith.constant -1 : index
%421 = arith.cmpi sle, %416, %417 : index
%418 = arith.select %421, %419, %420 : index
cf.br ^bb45(%416 : index)
^bb45(%422: index):
%423 = arith.cmpi slt, %422, %417 : index
%424 = arith.cmpi sgt, %422, %417 : index
%425 = arith.select %421, %423, %424 : i1
cf.cond_br %425, ^bb46(%422 : index), ^bb47(%422 : index)
^bb46(%426: index):
%427 = llvm.load %404 : !llvm.ptr -> i64
%428 = arith.constant 0 : i32
%429 = arith.index_cast %428 : i32 to index
%430 = arith.index_cast %427 : i32 to index
%432 = arith.constant 1 : index
%433 = arith.constant -1 : index
%434 = arith.cmpi sle, %429, %430 : index
%431 = arith.select %434, %432, %433 : index
cf.br ^bb48(%429 : index)
^bb48(%435: index):
%436 = arith.cmpi slt, %435, %430 : index
%437 = arith.cmpi sgt, %435, %430 : index
%438 = arith.select %434, %436, %437 : i1
cf.cond_br %438, ^bb49(%435 : index), ^bb50(%435 : index)
^bb49(%439: index):
%441 = arith.index_cast %439 : index to i64
%442 = llvm.getelementptr %336[%441] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%440 = llvm.load %442 : !llvm.ptr -> i64
%444 = arith.index_cast %426 : index to i64
%445 = llvm.getelementptr %331[%444] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%443 = llvm.load %445 : !llvm.ptr -> i32
%446 = arith.extsi %443 : i32 to i64
%447 = arith.muli %440, %446 : i64
%448 = llvm.load %404 : !llvm.ptr -> i64
%449 = llvm.getelementptr %336[%448] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %447, %449 : i64, !llvm.ptr
%451 = arith.index_cast %439 : index to i64
%452 = llvm.getelementptr %341[%451] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%450 = llvm.load %452 : !llvm.ptr -> i32
%453 = arith.constant 1 : i32
%454 = arith.xori %450, %453 : i32
%455 = llvm.load %404 : !llvm.ptr -> i64
%456 = llvm.getelementptr %341[%455] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %454, %456 : i32, !llvm.ptr
%457 = llvm.load %404 : !llvm.ptr -> i64
%458 = arith.constant 1 : i32
%460 = arith.extsi %458 : i32 to i64
%459 = arith.addi %457, %460 : i64
llvm.store %459, %404 : i64, !llvm.ptr
%461 = arith.addi %439, %431 : index
cf.br ^bb48(%461 : index)
^bb50(%462: index):
%463 = arith.addi %426, %418 : index
cf.br ^bb45(%463 : index)
^bb47(%464: index):
%465 = arith.constant 1 : i32
%466 = arith.extsi %465 : i32 to i64
%467 = llvm.mlir.constant(1 : i64) : i64
%468 = llvm.alloca %467 x i64 : (i64) -> !llvm.ptr
llvm.store %466, %468 : i64, !llvm.ptr
%469 = arith.constant 0 : i32
%470 = llvm.load %404 : !llvm.ptr -> i64
%471 = arith.index_cast %469 : i32 to index
%472 = arith.index_cast %470 : i32 to index
%474 = arith.constant 1 : index
%475 = arith.constant -1 : index
%476 = arith.cmpi sle, %471, %472 : index
%473 = arith.select %476, %474, %475 : index
cf.br ^bb51(%471 : index)
^bb51(%477: index):
%478 = arith.cmpi slt, %477, %472 : index
%479 = arith.cmpi sgt, %477, %472 : index
%480 = arith.select %476, %478, %479 : i1
cf.cond_br %480, ^bb52(%477 : index), ^bb53(%477 : index)
^bb52(%481: index):
%483 = arith.index_cast %481 : index to i64
%484 = llvm.getelementptr %336[%483] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%482 = llvm.load %484 : !llvm.ptr -> i64
%486 = arith.index_cast %362 : index to i32
%487 = arith.trunci %482 : i64 to i32
%485 = arith.divsi %486, %487 : i32
%488 = arith.extsi %485 : i32 to i64
%490 = arith.index_cast %481 : index to i64
%491 = llvm.getelementptr %341[%490] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%489 = llvm.load %491 : !llvm.ptr -> i32
%492 = arith.constant 0 : i32
%493 = arith.cmpi eq, %489, %492 : i32
cf.cond_br %493, ^bb54, ^bb55
^bb54:
%494 = llvm.load %468 : !llvm.ptr -> i64
%496 = llvm.getelementptr %157[%488] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%495 = llvm.load %496 : !llvm.ptr -> i64
%497 = arith.muli %494, %495 : i64
%498 = llvm.mlir.addressof @MOD : !llvm.ptr
%499 = llvm.load %498 : !llvm.ptr -> i64
%500 = arith.remsi %497, %499 : i64
llvm.store %500, %468 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
%501 = llvm.load %468 : !llvm.ptr -> i64
%503 = llvm.getelementptr %165[%488] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%502 = llvm.load %503 : !llvm.ptr -> i64
%504 = arith.muli %501, %502 : i64
%505 = llvm.mlir.addressof @MOD : !llvm.ptr
%506 = llvm.load %505 : !llvm.ptr -> i64
%507 = arith.remsi %504, %506 : i64
llvm.store %507, %468 : i64, !llvm.ptr
cf.br ^bb56
^bb56:
%508 = arith.addi %481, %473 : index
cf.br ^bb51(%508 : index)
^bb53(%509: index):
%510 = llvm.load %468 : !llvm.ptr -> i64
llvm.store %510, %366 : i64, !llvm.ptr
cf.br ^bb38
^bb38:
%511 = llvm.load %366 : !llvm.ptr -> i64
%512 = arith.constant 1 : i32
%514 = arith.extsi %512 : i32 to i64
%513 = arith.addi %511, %514 : i64
%515 = llvm.mlir.constant(1 : i64) : i64
%516 = llvm.alloca %515 x i64 : (i64) -> !llvm.ptr
llvm.store %513, %516 : i64, !llvm.ptr
%517 = llvm.load %516 : !llvm.ptr -> i64
%518 = llvm.mlir.addressof @MOD : !llvm.ptr
%519 = llvm.load %518 : !llvm.ptr -> i64
%520 = arith.cmpi sge, %517, %519 : i64
cf.cond_br %520, ^bb57, ^bb58
^bb57:
%521 = llvm.load %516 : !llvm.ptr -> i64
%522 = llvm.mlir.addressof @MOD : !llvm.ptr
%523 = llvm.load %522 : !llvm.ptr -> i64
%524 = arith.subi %521, %523 : i64
llvm.store %524, %516 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%525 = arith.index_cast %362 : index to i64
%526 = llvm.mlir.constant(1 : i64) : i64
%527 = llvm.alloca %526 x i64 : (i64) -> !llvm.ptr
llvm.store %525, %527 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%528 = llvm.load %527 : !llvm.ptr -> i64
%529 = llvm.mlir.addressof @N : !llvm.ptr
%530 = llvm.load %529 : !llvm.ptr -> i64
%531 = arith.cmpi sle, %528, %530 : i64
cf.cond_br %531, ^bb61, ^bb62
^bb61:
%533 = llvm.load %527 : !llvm.ptr -> i64
%534 = llvm.getelementptr %295[%533] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%532 = llvm.load %534 : !llvm.ptr -> i64
%535 = llvm.load %516 : !llvm.ptr -> i64
%536 = arith.muli %532, %535 : i64
%537 = llvm.mlir.addressof @MOD : !llvm.ptr
%538 = llvm.load %537 : !llvm.ptr -> i64
%539 = arith.remsi %536, %538 : i64
%540 = llvm.load %527 : !llvm.ptr -> i64
%541 = llvm.getelementptr %295[%540] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %539, %541 : i64, !llvm.ptr
%542 = llvm.load %527 : !llvm.ptr -> i64
%544 = arith.trunci %542 : i64 to i32
%545 = arith.index_cast %362 : index to i32
%543 = arith.addi %544, %545 : i32
%546 = arith.extsi %543 : i32 to i64
llvm.store %546, %527 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%547 = arith.addi %362, %354 : index
cf.br ^bb33(%547 : index)
^bb35(%548: index):
func.call @free(%331) : (!llvm.ptr) -> ()
func.call @free(%336) : (!llvm.ptr) -> ()
func.call @free(%341) : (!llvm.ptr) -> ()
func.call @free(%157) : (!llvm.ptr) -> ()
func.call @free(%165) : (!llvm.ptr) -> ()
func.call @free(%39) : (!llvm.ptr) -> ()
%555 = arith.constant 0 : i32
%556 = arith.extsi %555 : i32 to i64
%557 = llvm.mlir.constant(1 : i64) : i64
%558 = llvm.alloca %557 x i64 : (i64) -> !llvm.ptr
llvm.store %556, %558 : i64, !llvm.ptr
%559 = arith.constant 1 : i32
%560 = llvm.mlir.addressof @N : !llvm.ptr
%561 = llvm.load %560 : !llvm.ptr -> i64
%562 = arith.constant 1 : i32
%564 = arith.extsi %562 : i32 to i64
%563 = arith.addi %561, %564 : i64
%565 = arith.index_cast %559 : i32 to index
%566 = arith.index_cast %563 : i32 to index
%568 = arith.constant 1 : index
%569 = arith.constant -1 : index
%570 = arith.cmpi sle, %565, %566 : index
%567 = arith.select %570, %568, %569 : index
cf.br ^bb63(%565 : index)
^bb63(%571: index):
%572 = arith.cmpi slt, %571, %566 : index
%573 = arith.cmpi sgt, %571, %566 : index
%574 = arith.select %570, %572, %573 : i1
cf.cond_br %574, ^bb64(%571 : index), ^bb65(%571 : index)
^bb64(%575: index):
%576 = llvm.load %558 : !llvm.ptr -> i64
%578 = arith.index_cast %575 : index to i64
%579 = llvm.getelementptr %295[%578] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%577 = llvm.load %579 : !llvm.ptr -> i64
%580 = arith.addi %576, %577 : i64
llvm.store %580, %558 : i64, !llvm.ptr
%581 = llvm.load %558 : !llvm.ptr -> i64
%582 = llvm.mlir.addressof @MOD : !llvm.ptr
%583 = llvm.load %582 : !llvm.ptr -> i64
%584 = arith.cmpi sge, %581, %583 : i64
cf.cond_br %584, ^bb66, ^bb67
^bb66:
%585 = llvm.load %558 : !llvm.ptr -> i64
%586 = llvm.mlir.addressof @MOD : !llvm.ptr
%587 = llvm.load %586 : !llvm.ptr -> i64
%588 = arith.subi %585, %587 : i64
llvm.store %588, %558 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%589 = llvm.load %558 : !llvm.ptr -> i64
%590 = arith.index_cast %575 : index to i64
%591 = llvm.getelementptr %295[%590] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %589, %591 : i64, !llvm.ptr
%592 = arith.addi %575, %567 : index
cf.br ^bb63(%592 : index)
^bb65(%593: index):
%595 = llvm.mlir.addressof @N : !llvm.ptr
%596 = llvm.load %595 : !llvm.ptr -> i64
%597 = arith.constant 1 : i32
%599 = arith.extsi %597 : i32 to i64
%598 = arith.addi %596, %599 : i64
%600 = arith.constant 4 : i32
%601 = arith.extsi %600 : i32 to i64
%594 = func.call @calloc(%598, %601) : (i64, i64) -> !llvm.ptr
%602 = arith.constant 0 : i32
%603 = llvm.mlir.constant(1 : i64) : i64
%604 = llvm.alloca %603 x i32 : (i64) -> !llvm.ptr
llvm.store %602, %604 : i32, !llvm.ptr
%605 = arith.constant 1 : i32
%606 = llvm.mlir.addressof @N : !llvm.ptr
%607 = llvm.load %606 : !llvm.ptr -> i64
%608 = arith.constant 1 : i32
%610 = arith.extsi %608 : i32 to i64
%609 = arith.addi %607, %610 : i64
%611 = arith.index_cast %605 : i32 to index
%612 = arith.index_cast %609 : i32 to index
%614 = arith.constant 1 : index
%615 = arith.constant -1 : index
%616 = arith.cmpi sle, %611, %612 : index
%613 = arith.select %616, %614, %615 : index
cf.br ^bb69(%611 : index)
^bb69(%617: index):
%618 = arith.cmpi slt, %617, %612 : index
%619 = arith.cmpi sgt, %617, %612 : index
%620 = arith.select %616, %618, %619 : i1
cf.cond_br %620, ^bb70(%617 : index), ^bb71(%617 : index)
^bb70(%621: index):
%622 = llvm.load %604 : !llvm.ptr -> i32
%624 = arith.index_cast %621 : index to i64
%625 = llvm.getelementptr %47[%624] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%623 = llvm.load %625 : !llvm.ptr -> i8
%626 = arith.extsi %623 : i8 to i32
%627 = arith.addi %622, %626 : i32
llvm.store %627, %604 : i32, !llvm.ptr
%628 = llvm.load %604 : !llvm.ptr -> i32
%629 = arith.index_cast %621 : index to i64
%630 = llvm.getelementptr %594[%629] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %628, %630 : i32, !llvm.ptr
%631 = arith.addi %621, %613 : index
cf.br ^bb69(%631 : index)
^bb71(%632: index):
%633 = arith.constant 0 : i32
%634 = arith.extsi %633 : i32 to i64
%635 = llvm.mlir.constant(1 : i64) : i64
%636 = llvm.alloca %635 x i64 : (i64) -> !llvm.ptr
llvm.store %634, %636 : i64, !llvm.ptr
%637 = arith.constant 1 : i32
%638 = arith.extsi %637 : i32 to i64
%639 = llvm.mlir.constant(1 : i64) : i64
%640 = llvm.alloca %639 x i64 : (i64) -> !llvm.ptr
llvm.store %638, %640 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%641 = llvm.load %640 : !llvm.ptr -> i64
%642 = llvm.mlir.addressof @N : !llvm.ptr
%643 = llvm.load %642 : !llvm.ptr -> i64
%644 = arith.cmpi sle, %641, %643 : i64
cf.cond_br %644, ^bb73, ^bb74
^bb73:
%645 = llvm.mlir.addressof @N : !llvm.ptr
%646 = llvm.load %645 : !llvm.ptr -> i64
%647 = llvm.load %640 : !llvm.ptr -> i64
%648 = arith.divsi %646, %647 : i64
%649 = llvm.mlir.addressof @N : !llvm.ptr
%650 = llvm.load %649 : !llvm.ptr -> i64
%651 = arith.divsi %650, %648 : i64
%653 = llvm.getelementptr %594[%651] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%652 = llvm.load %653 : !llvm.ptr -> i32
%655 = llvm.load %640 : !llvm.ptr -> i64
%656 = arith.constant 1 : i32
%658 = arith.extsi %656 : i32 to i64
%657 = arith.subi %655, %658 : i64
%659 = llvm.getelementptr %594[%657] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%654 = llvm.load %659 : !llvm.ptr -> i32
%660 = arith.subi %652, %654 : i32
%661 = arith.extsi %660 : i32 to i64
%662 = llvm.mlir.addressof @MOD : !llvm.ptr
%663 = llvm.load %662 : !llvm.ptr -> i64
%664 = arith.remsi %661, %663 : i64
%666 = llvm.getelementptr %295[%648] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%665 = llvm.load %666 : !llvm.ptr -> i64
%667 = arith.muli %664, %665 : i64
%668 = llvm.load %636 : !llvm.ptr -> i64
%669 = arith.addi %668, %667 : i64
%670 = llvm.mlir.addressof @MOD : !llvm.ptr
%671 = llvm.load %670 : !llvm.ptr -> i64
%672 = arith.remsi %669, %671 : i64
llvm.store %672, %636 : i64, !llvm.ptr
%673 = arith.constant 1 : i32
%675 = arith.extsi %673 : i32 to i64
%674 = arith.addi %651, %675 : i64
llvm.store %674, %640 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%676 = llvm.load %636 : !llvm.ptr -> i64
%677 = llvm.mlir.addressof @MOD : !llvm.ptr
%678 = llvm.load %677 : !llvm.ptr -> i64
%679 = arith.remsi %676, %678 : i64
llvm.store %679, %636 : i64, !llvm.ptr
%680 = llvm.load %636 : !llvm.ptr -> i64
%681 = arith.constant 0 : i32
%683 = arith.extsi %681 : i32 to i64
%682 = arith.cmpi slt, %680, %683 : i64
cf.cond_br %682, ^bb75, ^bb76
^bb75:
%684 = llvm.load %636 : !llvm.ptr -> i64
%685 = llvm.mlir.addressof @MOD : !llvm.ptr
%686 = llvm.load %685 : !llvm.ptr -> i64
%687 = arith.addi %684, %686 : i64
llvm.store %687, %636 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
func.call @free(%594) : (!llvm.ptr) -> ()
func.call @free(%47) : (!llvm.ptr) -> ()
func.call @free(%55) : (!llvm.ptr) -> ()
func.call @free(%295) : (!llvm.ptr) -> ()
%692 = llvm.mlir.addressof @str_0 : !llvm.ptr
%693 = llvm.load %636 : !llvm.ptr -> i64
%694 = llvm.call @printf(%692, %693) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%695 = arith.constant 0 : i32
func.return %695 : i32
}
}