← All problems Problem 902
Compute P(100) mod 1e9+7. Port of the C reference solver.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 902: Permutation Powers
# Compute P(100) mod 1e9+7.
# Port of the C reference solver.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
import euler.nt { gcd, mod_pow }
const MOD: i64 = 1000000007
const A_VAL: i64 = 1000000007
const MM: i64 = 100
function inv_mod(a: i64, m: i64) -> i64 {
let mut x0: i64 = 1
let mut y0: i64 = 0
let mut x1: i64 = 0
let mut y1: i64 = 1
let mut aa: i64 = a % m
let mut bb: i64 = m
while bb != 0 {
let q: i64 = aa / bb
let r: i64 = aa - q * bb
aa = bb
bb = r
let tx: i64 = x0 - q * x1
x0 = x1
x1 = tx
}
if x0 < 0 {
x0 = x0 + m
}
if x0 >= m {
x0 = x0 % m
}
return x0
}
function lcm_upto_mod(m: i64) -> i64 {
let result: i64 = 1
let is_prime: ptr<i8> = calloc(m + 1, 1)
let mut i: i64 = 0
while i <= m {
is_prime[i] = 1
i = i + 1
}
is_prime[0] = 0
is_prime[1] = 0
i = 2
while i <= m {
if is_prime[i] == 1 {
let mut pk: i64 = 1
while pk * i <= m {
pk = pk * i
}
result = result * (pk % MOD) % MOD
let mut j: i64 = i * i
while j <= m {
is_prime[j] = 0
j = j + i
}
}
i = i + 1
}
free(is_prime)
return result
}
# Insertion sort for a subarray: arr[offset..offset+len-1]
function sort_sub(arr: ptr<i32>, offset: i64, len: i64) -> void {
let mut i: i64 = 1
while i < len {
let key: i32 = arr[offset + i]
let mut j: i64 = i
while j > 0 && arr[offset + j - 1] > key {
arr[offset + j] = arr[offset + j - 1]
j = j - 1
}
arr[offset + j] = key
i = i + 1
}
}
# lower_bound on subarray: first index where arr[offset+idx] >= val
function lower_bound_sub(arr: ptr<i32>, offset: i64, len: i64, val: i32) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = len
while lo < hi {
let mid: i64 = (lo + hi) / 2
if arr[offset + mid] < val {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
function main() -> i32 {
let m: i64 = MM
let n: i64 = m * (m + 1) / 2
# Precompute factorials mod MOD
let fact_n: ptr<i64> = calloc(n + 1, 8)
fact_n[0] = 1
fact_n[1] = 1
let mut i: i64 = 2
while i <= n {
fact_n[i] = fact_n[i - 1] * i % MOD
i = i + 1
}
# weights[i] = fact_n[n - i] for i = 1..n
let weights: ptr<i64> = calloc(n + 1, 8)
i = 1
while i <= n {
weights[i] = fact_n[n - i]
i = i + 1
}
# Build cycles: flat array, cycle_start[l] = l*(l-1)/2
let total_cycle_elems: i64 = m * (m + 1) / 2
let cycles_flat: ptr<i32> = calloc(total_cycle_elems + 1, 4)
let clen: ptr<i32> = calloc(n + 1, 4)
let coff: ptr<i32> = calloc(n + 1, 4)
let inva: i64 = inv_mod(A_VAL % n, n)
let mut l: i64 = 1
while l <= m {
let start: i64 = l * (l - 1) / 2 + 1
let cyc_start: i64 = l * (l - 1) / 2
let mut x: i64 = start
while x < start + l {
let t: i64 = (inva * ((x - 1) % n)) % n
if t == 0 {
cycles_flat[cyc_start + (x - start)] = n as i32
} else {
cycles_flat[cyc_start + (x - start)] = t as i32
}
x = x + 1
}
let mut idx: i64 = 0
while idx < l {
let elem: i64 = cycles_flat[cyc_start + idx] as i64
clen[elem] = l as i32
coff[elem] = idx as i32
idx = idx + 1
}
l = l + 1
}
# L mod MOD
let L_mod: i64 = lcm_upto_mod(m)
# Precompute gcd_tab, scale, comp (all flat)
let gcd_tab: ptr<i64> = calloc((MM + 1) * (MM + 1), 8)
let scale: ptr<i64> = calloc((MM + 1) * (MM + 1), 8)
let comp_flat: ptr<i32> = calloc((MM + 1) * (MM + 1) * MM, 4)
# Temporary buffers for building A_subs and B_sorted
let a_subs_buf: ptr<i32> = calloc(MM + 1, 4)
let b_sorted_buf: ptr<i32> = calloc(MM + 1, 4)
let a_off: ptr<i64> = calloc(MM + 1, 8)
let b_off: ptr<i64> = calloc(MM + 1, 8)
let a_cnt: ptr<i64> = calloc(MM + 1, 8)
let b_cnt: ptr<i64> = calloc(MM + 1, 8)
let mut a: i64 = 1
while a <= m {
let a_cyc_start: i64 = a * (a - 1) / 2
let mut b: i64 = 1
while b <= m {
let g: i64 = gcd(a, b)
gcd_tab[a * (MM + 1) + b] = g
let lcm_val: i64 = (a / g) * b
scale[a * (MM + 1) + b] = L_mod * mod_pow(lcm_val % MOD, MOD - 2, MOD) % MOD
let b_cyc_start: i64 = b * (b - 1) / 2
# Build a_subs and b_sorted for each residue class mod g
# Fill offsets and counts
let mut total_a: i64 = 0
let mut total_b: i64 = 0
let mut r: i64 = 0
while r < g {
a_off[r] = total_a
let mut ac: i64 = (a - r + g - 1) / g
if r >= a {
ac = 0
}
a_cnt[r] = ac
total_a = total_a + ac
b_off[r] = total_b
let mut bc: i64 = (b - r + g - 1) / g
if r >= b {
bc = 0
}
b_cnt[r] = bc
total_b = total_b + bc
r = r + 1
}
# Fill a_subs_buf and b_sorted_buf
r = 0
while r < g {
let mut cnt: i64 = 0
let mut idx2: i64 = r
while idx2 < a {
a_subs_buf[a_off[r] + cnt] = cycles_flat[a_cyc_start + idx2]
cnt = cnt + 1
idx2 = idx2 + g
}
cnt = 0
idx2 = r
while idx2 < b {
b_sorted_buf[b_off[r] + cnt] = cycles_flat[b_cyc_start + idx2]
cnt = cnt + 1
idx2 = idx2 + g
}
sort_sub(b_sorted_buf, b_off[r], b_cnt[r])
r = r + 1
}
# Compute smallcounts[d] for each d
let mut d: i64 = 0
while d < g {
let mut tot: i64 = 0
r = 0
while r < g {
let s: i64 = ((r - d) % g + g) % g
let bs_off: i64 = b_off[s]
let bs_len: i64 = b_cnt[s]
let mut idx2: i64 = 0
while idx2 < a_cnt[r] {
let aval: i32 = a_subs_buf[a_off[r] + idx2]
tot = tot + lower_bound_sub(b_sorted_buf, bs_off, bs_len, aval)
idx2 = idx2 + 1
}
r = r + 1
}
comp_flat[a * (MM + 1) * MM + b * MM + d] = tot as i32
d = d + 1
}
b = b + 1
}
a = a + 1
}
free(a_subs_buf)
free(b_sorted_buf)
free(a_off)
free(b_off)
free(a_cnt)
free(b_cnt)
# Sum of ranks over all exponents k mod L
let mut acc: i64 = 0
i = 1
while i < n {
let wi: i64 = weights[i]
let ai: i64 = clen[i] as i64
let offi: i64 = coff[i] as i64
let mut j: i64 = i + 1
while j <= n {
let aj: i64 = clen[j] as i64
let g: i64 = gcd_tab[ai * (MM + 1) + aj]
let mut d: i64 = 0
if g == 1 {
d = 0
} else {
d = ((offi - (coff[j] as i64)) % g + g) % g
}
let small: i64 = comp_flat[ai * (MM + 1) * MM + aj * MM + d] as i64
if small != 0 {
let cnt: i64 = scale[ai * (MM + 1) + aj] * small % MOD
acc = acc + wi * cnt
if acc >= 4611686018427387904 {
acc = acc % MOD
}
}
j = j + 1
}
i = i + 1
}
acc = acc % MOD
let sum_ranks_mod: i64 = (L_mod + acc) % MOD
# m! mod MOD
let mut m_fact: i64 = 1
let mut k: i64 = 2
while k <= m {
m_fact = m_fact * k % MOD
k = k + 1
}
let ans: i64 = sum_ranks_mod * m_fact % MOD * mod_pow(L_mod, MOD - 2, MOD) % MOD
printf("%lld\n", ans)
free(fact_n)
free(weights)
free(cycles_flat)
free(clen)
free(coff)
free(gcd_tab)
free(scale)
free(comp_flat)
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 gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t inv_mod_i64_i64(int64_t a, int64_t m);
int64_t lcm_upto_mod_i64(int64_t m);
void sort_sub_ptr_i32_i64_i64(int32_t* arr, int64_t offset, int64_t len);
int64_t lower_bound_sub_ptr_i32_i64_i64_i32(int32_t* arr, int64_t offset, int64_t len, int32_t val);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t A_VAL = 1000000007;
static const int64_t MM = 100;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t inv_mod_i64_i64(int64_t a, int64_t m) {
int64_t x0 = 1;
int64_t y0 = 0;
int64_t x1 = 0;
int64_t y1 = 1;
int64_t aa = FLOW_CHECKED_MOD((a), (m));
int64_t bb = m;
while (bb != 0) {
int64_t q = FLOW_CHECKED_DIV((aa), (bb));
int64_t r = (aa - (q * bb));
aa = bb;
bb = r;
int64_t tx = (x0 - (q * x1));
x0 = x1;
x1 = tx;
}
if (x0 < 0) {
x0 = (x0 + m);
}
if (x0 >= m) {
x0 = FLOW_CHECKED_MOD((x0), (m));
}
return x0;
}
int64_t lcm_upto_mod_i64(int64_t m) {
int64_t result = 1;
int8_t* is_prime = (int8_t*)(calloc((m + 1), 1));
int64_t i = 0;
while (i <= m) {
is_prime[i] = 1;
i = (i + 1);
}
is_prime[0] = 0;
is_prime[1] = 0;
i = 2;
while (i <= m) {
if (is_prime[i] == 1) {
int64_t pk = 1;
while ((pk * i) <= m) {
pk = (pk * i);
}
result = FLOW_CHECKED_MOD(((result * FLOW_CHECKED_MOD((pk), (MOD)))), (MOD));
int64_t j = (i * i);
while (j <= m) {
is_prime[j] = 0;
j = (j + i);
}
}
i = (i + 1);
}
free(is_prime);
return result;
}
void sort_sub_ptr_i32_i64_i64(int32_t* arr, int64_t offset, int64_t len) {
int64_t i = 1;
while (i < len) {
int32_t key = arr[(offset + i)];
int64_t j = i;
while ((j > 0 && arr[((offset + j) - 1)] > key)) {
arr[(offset + j)] = arr[((offset + j) - 1)];
j = (j - 1);
}
arr[(offset + j)] = key;
i = (i + 1);
}
}
int64_t lower_bound_sub_ptr_i32_i64_i64_i32(int32_t* arr, int64_t offset, int64_t len, int32_t val) {
int64_t lo = 0;
int64_t hi = len;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (arr[(offset + mid)] < val) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
int32_t main(void) {
int64_t m = MM;
int64_t n = FLOW_CHECKED_DIV(((m * (m + 1))), (2));
int64_t* fact_n = (int64_t*)(calloc((n + 1), 8));
fact_n[0] = 1;
fact_n[1] = 1;
int64_t i = 2;
while (i <= n) {
fact_n[i] = FLOW_CHECKED_MOD(((fact_n[(i - 1)] * i)), (MOD));
i = (i + 1);
}
int64_t* weights = (int64_t*)(calloc((n + 1), 8));
i = 1;
while (i <= n) {
weights[i] = fact_n[(n - i)];
i = (i + 1);
}
int64_t total_cycle_elems = FLOW_CHECKED_DIV(((m * (m + 1))), (2));
int32_t* cycles_flat = (int32_t*)(calloc((total_cycle_elems + 1), 4));
int32_t* clen = (int32_t*)(calloc((n + 1), 4));
int32_t* coff = (int32_t*)(calloc((n + 1), 4));
int64_t inva = inv_mod_i64_i64(FLOW_CHECKED_MOD((A_VAL), (n)), n);
int64_t l = 1;
while (l <= m) {
int64_t start = (FLOW_CHECKED_DIV(((l * (l - 1))), (2)) + 1);
int64_t cyc_start = FLOW_CHECKED_DIV(((l * (l - 1))), (2));
int64_t x = start;
while (x < (start + l)) {
int64_t t = FLOW_CHECKED_MOD(((inva * FLOW_CHECKED_MOD(((x - 1)), (n)))), (n));
if (t == 0) {
cycles_flat[(cyc_start + (x - start))] = ((int32_t)(n));
} else {
cycles_flat[(cyc_start + (x - start))] = ((int32_t)(t));
}
x = (x + 1);
}
int64_t idx = 0;
while (idx < l) {
int64_t elem = ((int64_t)(cycles_flat[(cyc_start + idx)]));
clen[elem] = ((int32_t)(l));
coff[elem] = ((int32_t)(idx));
idx = (idx + 1);
}
l = (l + 1);
}
int64_t L_mod = lcm_upto_mod_i64(m);
int64_t* gcd_tab = (int64_t*)(calloc(((MM + 1) * (MM + 1)), 8));
int64_t* scale = (int64_t*)(calloc(((MM + 1) * (MM + 1)), 8));
int32_t* comp_flat = (int32_t*)(calloc((((MM + 1) * (MM + 1)) * MM), 4));
int32_t* a_subs_buf = (int32_t*)(calloc((MM + 1), 4));
int32_t* b_sorted_buf = (int32_t*)(calloc((MM + 1), 4));
int64_t* a_off = (int64_t*)(calloc((MM + 1), 8));
int64_t* b_off = (int64_t*)(calloc((MM + 1), 8));
int64_t* a_cnt = (int64_t*)(calloc((MM + 1), 8));
int64_t* b_cnt = (int64_t*)(calloc((MM + 1), 8));
int64_t a = 1;
while (a <= m) {
int64_t a_cyc_start = FLOW_CHECKED_DIV(((a * (a - 1))), (2));
int64_t b = 1;
while (b <= m) {
int64_t g = gcd_i64_i64(a, b);
gcd_tab[((a * (MM + 1)) + b)] = g;
int64_t lcm_val = (FLOW_CHECKED_DIV((a), (g)) * b);
scale[((a * (MM + 1)) + b)] = FLOW_CHECKED_MOD(((L_mod * mod_pow_i64_i64_i64(FLOW_CHECKED_MOD((lcm_val), (MOD)), (MOD - 2), MOD))), (MOD));
int64_t b_cyc_start = FLOW_CHECKED_DIV(((b * (b - 1))), (2));
int64_t total_a = 0;
int64_t total_b = 0;
int64_t r = 0;
while (r < g) {
a_off[r] = total_a;
int64_t ac = FLOW_CHECKED_DIV(((((a - r) + g) - 1)), (g));
if (r >= a) {
ac = 0;
}
a_cnt[r] = ac;
total_a = (total_a + ac);
b_off[r] = total_b;
int64_t bc = FLOW_CHECKED_DIV(((((b - r) + g) - 1)), (g));
if (r >= b) {
bc = 0;
}
b_cnt[r] = bc;
total_b = (total_b + bc);
r = (r + 1);
}
r = 0;
while (r < g) {
int64_t cnt = 0;
int64_t idx2 = r;
while (idx2 < a) {
a_subs_buf[(a_off[r] + cnt)] = cycles_flat[(a_cyc_start + idx2)];
cnt = (cnt + 1);
idx2 = (idx2 + g);
}
cnt = 0;
idx2 = r;
while (idx2 < b) {
b_sorted_buf[(b_off[r] + cnt)] = cycles_flat[(b_cyc_start + idx2)];
cnt = (cnt + 1);
idx2 = (idx2 + g);
}
sort_sub_ptr_i32_i64_i64(b_sorted_buf, b_off[r], b_cnt[r]);
r = (r + 1);
}
int64_t d = 0;
while (d < g) {
int64_t tot = 0;
r = 0;
while (r < g) {
int64_t s = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((r - d)), (g)) + g)), (g));
int64_t bs_off = b_off[s];
int64_t bs_len = b_cnt[s];
int64_t idx2 = 0;
while (idx2 < a_cnt[r]) {
int32_t aval = a_subs_buf[(a_off[r] + idx2)];
tot = (tot + lower_bound_sub_ptr_i32_i64_i64_i32(b_sorted_buf, bs_off, bs_len, aval));
idx2 = (idx2 + 1);
}
r = (r + 1);
}
comp_flat[((((a * (MM + 1)) * MM) + (b * MM)) + d)] = ((int32_t)(tot));
d = (d + 1);
}
b = (b + 1);
}
a = (a + 1);
}
free(a_subs_buf);
free(b_sorted_buf);
free(a_off);
free(b_off);
free(a_cnt);
free(b_cnt);
int64_t acc = 0;
i = 1;
while (i < n) {
int64_t wi = weights[i];
int64_t ai = ((int64_t)(clen[i]));
int64_t offi = ((int64_t)(coff[i]));
int64_t j = (i + 1);
while (j <= n) {
int64_t aj = ((int64_t)(clen[j]));
int64_t g = gcd_tab[((ai * (MM + 1)) + aj)];
int64_t d = 0;
if (g == 1) {
d = 0;
} else {
d = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((offi - ((int64_t)(coff[j])))), (g)) + g)), (g));
}
int64_t small = ((int64_t)(comp_flat[((((ai * (MM + 1)) * MM) + (aj * MM)) + d)]));
if (small != 0) {
int64_t cnt = FLOW_CHECKED_MOD(((scale[((ai * (MM + 1)) + aj)] * small)), (MOD));
acc = (acc + (wi * cnt));
if (acc >= 4611686018427387904) {
acc = FLOW_CHECKED_MOD((acc), (MOD));
}
}
j = (j + 1);
}
i = (i + 1);
}
acc = FLOW_CHECKED_MOD((acc), (MOD));
int64_t sum_ranks_mod = FLOW_CHECKED_MOD(((L_mod + acc)), (MOD));
int64_t m_fact = 1;
int64_t k = 2;
while (k <= m) {
m_fact = FLOW_CHECKED_MOD(((m_fact * k)), (MOD));
k = (k + 1);
}
int64_t ans = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((sum_ranks_mod * m_fact)), (MOD)) * mod_pow_i64_i64_i64(L_mod, (MOD - 2), MOD))), (MOD));
printf("%lld\n", ans);
free(fact_n);
free(weights);
free(cycles_flat);
free(clen);
free(coff);
free(gcd_tab);
free(scale);
free(comp_flat);
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 @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi eq, %arg0, %15 : i64
%16 = scf.if %14 -> (i1) {
%17 = arith.constant true
scf.yield %17 : i1
} else {
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %arg1, %20 : i64
scf.yield %19 : i1
}
cf.cond_br %16, ^bb3, ^bb4
^bb3:
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i64
func.return %22 : i64
^bb4:
cf.br ^bb5
^bb5:
%23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
%24 = arith.divsi %arg0, %23 : i64
%25 = arith.muli %24, %arg1 : i64
func.return %25 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%26 = arith.constant 2 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %30 : i64, !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
%35 = arith.constant 2 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %36, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.cmpi slt, %40, %41 : i64
cf.cond_br %42, ^bb10, ^bb11
^bb10:
%43 = llvm.load %39 : !llvm.ptr -> i64
llvm.store %43, %30 : i64, !llvm.ptr
%44 = llvm.load %30 : !llvm.ptr -> i64
%45 = llvm.load %30 : !llvm.ptr -> i64
%46 = arith.divsi %arg0, %45 : i64
%47 = arith.addi %44, %46 : i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%51 = llvm.load %30 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.remsi %arg0, %arg2 : i64
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %54 : i64, !llvm.ptr
%55 = arith.remsi %arg1, %arg2 : i64
%56 = llvm.mlir.constant(1 : i64) : i64
%57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
llvm.store %55, %57 : i64, !llvm.ptr
%58 = arith.constant 0 : i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%62 = llvm.load %57 : !llvm.ptr -> i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%66 = llvm.load %57 : !llvm.ptr -> i64
%67 = arith.constant 2 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.remsi %66, %69 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi eq, %68, %72 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%73 = llvm.load %61 : !llvm.ptr -> i64
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = arith.addi %73, %74 : i64
%76 = arith.remsi %75, %arg2 : i64
llvm.store %76, %61 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%77 = llvm.load %54 : !llvm.ptr -> i64
%78 = arith.constant 2 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.muli %77, %80 : i64
%81 = arith.remsi %79, %arg2 : i64
llvm.store %81, %54 : i64, !llvm.ptr
%82 = llvm.load %57 : !llvm.ptr -> i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %82, %85 : i64
llvm.store %84, %57 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%86 = llvm.load %61 : !llvm.ptr -> i64
func.return %86 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi eq, %arg2, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
func.return %91 : i64
^bb19:
cf.br ^bb20
^bb20:
%92 = arith.constant 1 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.remsi %arg0, %arg2 : i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.constant 0 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sgt, %101, %104 : i64
cf.cond_br %103, ^bb22, ^bb23
^bb22:
%105 = llvm.load %100 : !llvm.ptr -> i64
%106 = arith.constant 2 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %105, %108 : i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi eq, %107, %111 : i64
cf.cond_br %110, ^bb24, ^bb25
^bb24:
%113 = llvm.load %95 : !llvm.ptr -> i64
%114 = llvm.load %98 : !llvm.ptr -> i64
%112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
llvm.store %112, %95 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%116 = llvm.load %98 : !llvm.ptr -> i64
%117 = llvm.load %98 : !llvm.ptr -> i64
%115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
llvm.store %115, %98 : i64, !llvm.ptr
%118 = llvm.load %100 : !llvm.ptr -> i64
%119 = arith.constant 2 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.divsi %118, %121 : i64
llvm.store %120, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%122 = llvm.load %95 : !llvm.ptr -> i64
func.return %122 : i64
}
func.func @is_prime(%arg0: i64) -> i1 {
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi slt, %arg0, %125 : i64
cf.cond_br %124, ^bb27, ^bb28
^bb27:
%126 = arith.constant 0 : i1
func.return %126 : i1
^bb28:
cf.br ^bb29
^bb29:
%127 = arith.constant 4 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi slt, %arg0, %129 : i64
cf.cond_br %128, ^bb30, ^bb31
^bb30:
%130 = arith.constant 1 : i1
func.return %130 : i1
^bb31:
cf.br ^bb32
^bb32:
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.remsi %arg0, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi eq, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = arith.constant 3 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.remsi %arg0, %141 : i64
%142 = arith.constant 0 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %140, %144 : i64
scf.yield %143 : i1
}
cf.cond_br %137, ^bb33, ^bb34
^bb33:
%145 = arith.constant 0 : i1
func.return %145 : i1
^bb34:
cf.br ^bb35
^bb35:
%146 = arith.constant 5 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %149 : !llvm.ptr -> i64
%152 = arith.muli %150, %151 : i64
%153 = arith.cmpi sle, %152, %arg0 : i64
cf.cond_br %153, ^bb37, ^bb38
^bb37:
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = arith.remsi %arg0, %154 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %155, %158 : i64
%159 = scf.if %157 -> (i1) {
%160 = arith.constant true
scf.yield %160 : i1
} else {
%161 = llvm.load %149 : !llvm.ptr -> i64
%162 = arith.constant 2 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.addi %161, %164 : i64
%165 = arith.remsi %arg0, %163 : i64
%166 = arith.constant 0 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.cmpi eq, %165, %168 : i64
scf.yield %167 : i1
}
cf.cond_br %159, ^bb39, ^bb40
^bb39:
%169 = arith.constant 0 : i1
func.return %169 : i1
^bb40:
cf.br ^bb41
^bb41:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = arith.constant 6 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%174 = arith.constant 1 : i1
func.return %174 : i1
}
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: A_VAL
llvm.mlir.global internal constant @A_VAL(1000000007 : i64) : i64
// Constant: MM
llvm.mlir.global internal constant @MM(100 : i64) : i64
func.func @inv_mod(%arg0: i64, %arg1: i64) -> i64 {
%175 = arith.constant 1 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %176, %178 : i64, !llvm.ptr
%179 = arith.constant 0 : i32
%180 = arith.extsi %179 : i32 to i64
%181 = llvm.mlir.constant(1 : i64) : i64
%182 = llvm.alloca %181 x i64 : (i64) -> !llvm.ptr
llvm.store %180, %182 : i64, !llvm.ptr
%183 = arith.constant 0 : i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
%187 = arith.constant 1 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.mlir.constant(1 : i64) : i64
%190 = llvm.alloca %189 x i64 : (i64) -> !llvm.ptr
llvm.store %188, %190 : i64, !llvm.ptr
%191 = arith.remsi %arg0, %arg1 : 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 = llvm.mlir.constant(1 : i64) : i64
%195 = llvm.alloca %194 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %195 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%196 = llvm.load %195 : !llvm.ptr -> i64
%197 = arith.constant 0 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.cmpi ne, %196, %199 : i64
cf.cond_br %198, ^bb43, ^bb44
^bb43:
%200 = llvm.load %193 : !llvm.ptr -> i64
%201 = llvm.load %195 : !llvm.ptr -> i64
%202 = arith.divsi %200, %201 : i64
%203 = llvm.load %193 : !llvm.ptr -> i64
%204 = llvm.load %195 : !llvm.ptr -> i64
%205 = arith.muli %202, %204 : i64
%206 = arith.subi %203, %205 : i64
%207 = llvm.load %195 : !llvm.ptr -> i64
llvm.store %207, %193 : i64, !llvm.ptr
llvm.store %206, %195 : i64, !llvm.ptr
%208 = llvm.load %178 : !llvm.ptr -> i64
%209 = llvm.load %186 : !llvm.ptr -> i64
%210 = arith.muli %202, %209 : i64
%211 = arith.subi %208, %210 : i64
%212 = llvm.load %186 : !llvm.ptr -> i64
llvm.store %212, %178 : i64, !llvm.ptr
llvm.store %211, %186 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%213 = llvm.load %178 : !llvm.ptr -> i64
%214 = arith.constant 0 : i32
%216 = arith.extsi %214 : i32 to i64
%215 = arith.cmpi slt, %213, %216 : i64
cf.cond_br %215, ^bb45, ^bb46
^bb45:
%217 = llvm.load %178 : !llvm.ptr -> i64
%218 = arith.addi %217, %arg1 : i64
llvm.store %218, %178 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%219 = llvm.load %178 : !llvm.ptr -> i64
%220 = arith.cmpi sge, %219, %arg1 : i64
cf.cond_br %220, ^bb48, ^bb49
^bb48:
%221 = llvm.load %178 : !llvm.ptr -> i64
%222 = arith.remsi %221, %arg1 : i64
llvm.store %222, %178 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%223 = llvm.load %178 : !llvm.ptr -> i64
func.return %223 : i64
}
func.func @lcm_upto_mod(%arg0: i64) -> i64 {
%224 = arith.constant 1 : i32
%225 = arith.extsi %224 : i32 to i64
%227 = arith.constant 1 : i32
%229 = arith.extsi %227 : i32 to i64
%228 = arith.addi %arg0, %229 : i64
%230 = arith.constant 1 : i32
%231 = arith.extsi %230 : i32 to i64
%226 = func.call @calloc(%228, %231) : (i64, i64) -> !llvm.ptr
%232 = arith.constant 0 : i32
%233 = arith.extsi %232 : i32 to i64
%234 = llvm.mlir.constant(1 : i64) : i64
%235 = llvm.alloca %234 x i64 : (i64) -> !llvm.ptr
llvm.store %233, %235 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%236 = llvm.load %235 : !llvm.ptr -> i64
%237 = arith.cmpi sle, %236, %arg0 : i64
cf.cond_br %237, ^bb52, ^bb53
^bb52:
%238 = arith.constant 1 : i32
%239 = llvm.load %235 : !llvm.ptr -> i64
%240 = arith.trunci %238 : i32 to i8
%241 = llvm.getelementptr %226[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %240, %241 : i8, !llvm.ptr
%242 = llvm.load %235 : !llvm.ptr -> i64
%243 = arith.constant 1 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.addi %242, %245 : i64
llvm.store %244, %235 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%246 = arith.constant 0 : i32
%247 = arith.constant 0 : i32
%248 = arith.trunci %246 : i32 to i8
%249 = arith.extsi %247 : i32 to i64
%250 = llvm.getelementptr %226[%249] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %248, %250 : i8, !llvm.ptr
%251 = arith.constant 0 : i32
%252 = arith.constant 1 : i32
%253 = arith.trunci %251 : i32 to i8
%254 = arith.extsi %252 : i32 to i64
%255 = llvm.getelementptr %226[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %253, %255 : i8, !llvm.ptr
%256 = arith.constant 2 : i32
%257 = arith.extsi %256 : i32 to i64
llvm.store %257, %235 : i64, !llvm.ptr
cf.br ^bb54(%225 : i64)
^bb54(%258: i64):
%259 = llvm.load %235 : !llvm.ptr -> i64
%260 = arith.cmpi sle, %259, %arg0 : i64
cf.cond_br %260, ^bb55(%258 : i64), ^bb56(%258 : i64)
^bb55(%261: i64):
%263 = llvm.load %235 : !llvm.ptr -> i64
%264 = llvm.getelementptr %226[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%262 = llvm.load %264 : !llvm.ptr -> i8
%265 = arith.constant 1 : i32
%267 = arith.extsi %262 : i8 to i32
%266 = arith.cmpi eq, %267, %265 : i32
cf.cond_br %266, ^bb57, ^bb58
^bb57:
%268 = arith.constant 1 : i32
%269 = arith.extsi %268 : i32 to i64
%270 = llvm.mlir.constant(1 : i64) : i64
%271 = llvm.alloca %270 x i64 : (i64) -> !llvm.ptr
llvm.store %269, %271 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%272 = llvm.load %271 : !llvm.ptr -> i64
%273 = llvm.load %235 : !llvm.ptr -> i64
%274 = arith.muli %272, %273 : i64
%275 = arith.cmpi sle, %274, %arg0 : i64
cf.cond_br %275, ^bb61, ^bb62
^bb61:
%276 = llvm.load %271 : !llvm.ptr -> i64
%277 = llvm.load %235 : !llvm.ptr -> i64
%278 = arith.muli %276, %277 : i64
llvm.store %278, %271 : i64, !llvm.ptr
cf.br ^bb60
^bb62:
%279 = llvm.load %271 : !llvm.ptr -> i64
%280 = llvm.mlir.addressof @MOD : !llvm.ptr
%281 = llvm.load %280 : !llvm.ptr -> i64
%282 = arith.remsi %279, %281 : i64
%283 = arith.muli %261, %282 : i64
%284 = llvm.mlir.addressof @MOD : !llvm.ptr
%285 = llvm.load %284 : !llvm.ptr -> i64
%286 = arith.remsi %283, %285 : i64
%287 = llvm.load %235 : !llvm.ptr -> i64
%288 = llvm.load %235 : !llvm.ptr -> i64
%289 = arith.muli %287, %288 : i64
%290 = llvm.mlir.constant(1 : i64) : i64
%291 = llvm.alloca %290 x i64 : (i64) -> !llvm.ptr
llvm.store %289, %291 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%292 = llvm.load %291 : !llvm.ptr -> i64
%293 = arith.cmpi sle, %292, %arg0 : i64
cf.cond_br %293, ^bb64, ^bb65
^bb64:
%294 = arith.constant 0 : i32
%295 = llvm.load %291 : !llvm.ptr -> i64
%296 = arith.trunci %294 : i32 to i8
%297 = llvm.getelementptr %226[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %296, %297 : i8, !llvm.ptr
%298 = llvm.load %291 : !llvm.ptr -> i64
%299 = llvm.load %235 : !llvm.ptr -> i64
%300 = arith.addi %298, %299 : i64
llvm.store %300, %291 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
cf.br ^bb59(%286 : i64)
^bb58:
cf.br ^bb59(%261 : i64)
^bb59(%301: i64):
%302 = llvm.load %235 : !llvm.ptr -> i64
%303 = arith.constant 1 : i32
%305 = arith.extsi %303 : i32 to i64
%304 = arith.addi %302, %305 : i64
llvm.store %304, %235 : i64, !llvm.ptr
cf.br ^bb54(%301 : i64)
^bb56(%306: i64):
func.call @free(%226) : (!llvm.ptr) -> ()
func.return %306 : i64
}
func.func @sort_sub(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> () {
%308 = arith.constant 1 : i32
%309 = arith.extsi %308 : i32 to i64
%310 = llvm.mlir.constant(1 : i64) : i64
%311 = llvm.alloca %310 x i64 : (i64) -> !llvm.ptr
llvm.store %309, %311 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%312 = llvm.load %311 : !llvm.ptr -> i64
%313 = arith.cmpi slt, %312, %arg2 : i64
cf.cond_br %313, ^bb67, ^bb68
^bb67:
%315 = llvm.load %311 : !llvm.ptr -> i64
%316 = arith.addi %arg1, %315 : i64
%317 = llvm.getelementptr %arg0[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%314 = llvm.load %317 : !llvm.ptr -> i32
%318 = llvm.load %311 : !llvm.ptr -> i64
%319 = llvm.mlir.constant(1 : i64) : i64
%320 = llvm.alloca %319 x i64 : (i64) -> !llvm.ptr
llvm.store %318, %320 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%321 = llvm.load %320 : !llvm.ptr -> i64
%322 = arith.constant 0 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.cmpi sgt, %321, %324 : i64
%325 = scf.if %323 -> (i1) {
%327 = llvm.load %320 : !llvm.ptr -> i64
%328 = arith.addi %arg1, %327 : i64
%329 = arith.constant 1 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.subi %328, %331 : i64
%332 = llvm.getelementptr %arg0[%330] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%326 = llvm.load %332 : !llvm.ptr -> i32
%333 = arith.cmpi sgt, %326, %314 : i32
scf.yield %333 : i1
} else {
%334 = arith.constant false
scf.yield %334 : i1
}
cf.cond_br %325, ^bb70, ^bb71
^bb70:
%336 = llvm.load %320 : !llvm.ptr -> i64
%337 = arith.addi %arg1, %336 : i64
%338 = arith.constant 1 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.subi %337, %340 : i64
%341 = llvm.getelementptr %arg0[%339] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%335 = llvm.load %341 : !llvm.ptr -> i32
%342 = llvm.load %320 : !llvm.ptr -> i64
%343 = arith.addi %arg1, %342 : i64
%344 = llvm.getelementptr %arg0[%343] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %335, %344 : i32, !llvm.ptr
%345 = llvm.load %320 : !llvm.ptr -> i64
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.subi %345, %348 : i64
llvm.store %347, %320 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%349 = llvm.load %320 : !llvm.ptr -> i64
%350 = arith.addi %arg1, %349 : i64
%351 = llvm.getelementptr %arg0[%350] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %314, %351 : i32, !llvm.ptr
%352 = llvm.load %311 : !llvm.ptr -> i64
%353 = arith.constant 1 : i32
%355 = arith.extsi %353 : i32 to i64
%354 = arith.addi %352, %355 : i64
llvm.store %354, %311 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
func.return
}
func.func @lower_bound_sub(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64, %arg3: i32) -> i64 {
%356 = arith.constant 0 : i32
%357 = arith.extsi %356 : i32 to i64
%358 = llvm.mlir.constant(1 : i64) : i64
%359 = llvm.alloca %358 x i64 : (i64) -> !llvm.ptr
llvm.store %357, %359 : i64, !llvm.ptr
%360 = llvm.mlir.constant(1 : i64) : i64
%361 = llvm.alloca %360 x i64 : (i64) -> !llvm.ptr
llvm.store %arg2, %361 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%362 = llvm.load %359 : !llvm.ptr -> i64
%363 = llvm.load %361 : !llvm.ptr -> i64
%364 = arith.cmpi slt, %362, %363 : i64
cf.cond_br %364, ^bb73, ^bb74
^bb73:
%365 = llvm.load %359 : !llvm.ptr -> i64
%366 = llvm.load %361 : !llvm.ptr -> i64
%367 = arith.addi %365, %366 : i64
%368 = arith.constant 2 : i32
%370 = arith.extsi %368 : i32 to i64
%369 = arith.divsi %367, %370 : i64
%372 = arith.addi %arg1, %369 : i64
%373 = llvm.getelementptr %arg0[%372] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%371 = llvm.load %373 : !llvm.ptr -> i32
%374 = arith.cmpi slt, %371, %arg3 : i32
cf.cond_br %374, ^bb75, ^bb76
^bb75:
%375 = arith.constant 1 : i32
%377 = arith.extsi %375 : i32 to i64
%376 = arith.addi %369, %377 : i64
llvm.store %376, %359 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
llvm.store %369, %361 : i64, !llvm.ptr
cf.br ^bb77
^bb77:
cf.br ^bb72
^bb74:
%378 = llvm.load %359 : !llvm.ptr -> i64
func.return %378 : i64
}
func.func @main() -> i32 {
%379 = llvm.mlir.addressof @MM : !llvm.ptr
%380 = llvm.load %379 : !llvm.ptr -> i64
%381 = arith.constant 1 : i32
%383 = arith.extsi %381 : i32 to i64
%382 = arith.addi %380, %383 : i64
%384 = arith.muli %380, %382 : i64
%385 = arith.constant 2 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.divsi %384, %387 : i64
%389 = arith.constant 1 : i32
%391 = arith.extsi %389 : i32 to i64
%390 = arith.addi %386, %391 : i64
%392 = arith.constant 8 : i32
%393 = arith.extsi %392 : i32 to i64
%388 = func.call @calloc(%390, %393) : (i64, i64) -> !llvm.ptr
%394 = arith.constant 1 : i32
%395 = arith.constant 0 : i32
%396 = arith.extsi %394 : i32 to i64
%397 = arith.extsi %395 : i32 to i64
%398 = llvm.getelementptr %388[%397] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %396, %398 : i64, !llvm.ptr
%399 = arith.constant 1 : i32
%400 = arith.constant 1 : i32
%401 = arith.extsi %399 : i32 to i64
%402 = arith.extsi %400 : i32 to i64
%403 = llvm.getelementptr %388[%402] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %401, %403 : i64, !llvm.ptr
%404 = arith.constant 2 : i32
%405 = arith.extsi %404 : i32 to i64
%406 = llvm.mlir.constant(1 : i64) : i64
%407 = llvm.alloca %406 x i64 : (i64) -> !llvm.ptr
llvm.store %405, %407 : i64, !llvm.ptr
cf.br ^bb78
^bb78:
%408 = llvm.load %407 : !llvm.ptr -> i64
%409 = arith.cmpi sle, %408, %386 : i64
cf.cond_br %409, ^bb79, ^bb80
^bb79:
%411 = llvm.load %407 : !llvm.ptr -> i64
%412 = arith.constant 1 : i32
%414 = arith.extsi %412 : i32 to i64
%413 = arith.subi %411, %414 : i64
%415 = llvm.getelementptr %388[%413] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%410 = llvm.load %415 : !llvm.ptr -> i64
%416 = llvm.load %407 : !llvm.ptr -> i64
%417 = arith.muli %410, %416 : i64
%418 = llvm.mlir.addressof @MOD : !llvm.ptr
%419 = llvm.load %418 : !llvm.ptr -> i64
%420 = arith.remsi %417, %419 : i64
%421 = llvm.load %407 : !llvm.ptr -> i64
%422 = llvm.getelementptr %388[%421] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %420, %422 : i64, !llvm.ptr
%423 = llvm.load %407 : !llvm.ptr -> i64
%424 = arith.constant 1 : i32
%426 = arith.extsi %424 : i32 to i64
%425 = arith.addi %423, %426 : i64
llvm.store %425, %407 : i64, !llvm.ptr
cf.br ^bb78
^bb80:
%428 = arith.constant 1 : i32
%430 = arith.extsi %428 : i32 to i64
%429 = arith.addi %386, %430 : i64
%431 = arith.constant 8 : i32
%432 = arith.extsi %431 : i32 to i64
%427 = func.call @calloc(%429, %432) : (i64, i64) -> !llvm.ptr
%433 = arith.constant 1 : i32
%434 = arith.extsi %433 : i32 to i64
llvm.store %434, %407 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%435 = llvm.load %407 : !llvm.ptr -> i64
%436 = arith.cmpi sle, %435, %386 : i64
cf.cond_br %436, ^bb82, ^bb83
^bb82:
%438 = llvm.load %407 : !llvm.ptr -> i64
%439 = arith.subi %386, %438 : i64
%440 = llvm.getelementptr %388[%439] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%437 = llvm.load %440 : !llvm.ptr -> i64
%441 = llvm.load %407 : !llvm.ptr -> i64
%442 = llvm.getelementptr %427[%441] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %437, %442 : i64, !llvm.ptr
%443 = llvm.load %407 : !llvm.ptr -> i64
%444 = arith.constant 1 : i32
%446 = arith.extsi %444 : i32 to i64
%445 = arith.addi %443, %446 : i64
llvm.store %445, %407 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%447 = arith.constant 1 : i32
%449 = arith.extsi %447 : i32 to i64
%448 = arith.addi %380, %449 : i64
%450 = arith.muli %380, %448 : i64
%451 = arith.constant 2 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.divsi %450, %453 : i64
%455 = arith.constant 1 : i32
%457 = arith.extsi %455 : i32 to i64
%456 = arith.addi %452, %457 : i64
%458 = arith.constant 4 : i32
%459 = arith.extsi %458 : i32 to i64
%454 = func.call @calloc(%456, %459) : (i64, i64) -> !llvm.ptr
%461 = arith.constant 1 : i32
%463 = arith.extsi %461 : i32 to i64
%462 = arith.addi %386, %463 : i64
%464 = arith.constant 4 : i32
%465 = arith.extsi %464 : i32 to i64
%460 = func.call @calloc(%462, %465) : (i64, i64) -> !llvm.ptr
%467 = arith.constant 1 : i32
%469 = arith.extsi %467 : i32 to i64
%468 = arith.addi %386, %469 : i64
%470 = arith.constant 4 : i32
%471 = arith.extsi %470 : i32 to i64
%466 = func.call @calloc(%468, %471) : (i64, i64) -> !llvm.ptr
%473 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%474 = llvm.load %473 : !llvm.ptr -> i64
%475 = arith.remsi %474, %386 : i64
%472 = func.call @inv_mod(%475, %386) : (i64, i64) -> i64
%476 = arith.constant 1 : i32
%477 = arith.extsi %476 : i32 to i64
%478 = llvm.mlir.constant(1 : i64) : i64
%479 = llvm.alloca %478 x i64 : (i64) -> !llvm.ptr
llvm.store %477, %479 : i64, !llvm.ptr
cf.br ^bb84
^bb84:
%480 = llvm.load %479 : !llvm.ptr -> i64
%481 = arith.cmpi sle, %480, %380 : i64
cf.cond_br %481, ^bb85, ^bb86
^bb85:
%482 = llvm.load %479 : !llvm.ptr -> i64
%483 = llvm.load %479 : !llvm.ptr -> i64
%484 = arith.constant 1 : i32
%486 = arith.extsi %484 : i32 to i64
%485 = arith.subi %483, %486 : i64
%487 = arith.muli %482, %485 : i64
%488 = arith.constant 2 : i32
%490 = arith.extsi %488 : i32 to i64
%489 = arith.divsi %487, %490 : i64
%491 = arith.constant 1 : i32
%493 = arith.extsi %491 : i32 to i64
%492 = arith.addi %489, %493 : i64
%494 = llvm.load %479 : !llvm.ptr -> i64
%495 = llvm.load %479 : !llvm.ptr -> i64
%496 = arith.constant 1 : i32
%498 = arith.extsi %496 : i32 to i64
%497 = arith.subi %495, %498 : i64
%499 = arith.muli %494, %497 : i64
%500 = arith.constant 2 : i32
%502 = arith.extsi %500 : i32 to i64
%501 = arith.divsi %499, %502 : i64
%503 = llvm.mlir.constant(1 : i64) : i64
%504 = llvm.alloca %503 x i64 : (i64) -> !llvm.ptr
llvm.store %492, %504 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%505 = llvm.load %504 : !llvm.ptr -> i64
%506 = llvm.load %479 : !llvm.ptr -> i64
%507 = arith.addi %492, %506 : i64
%508 = arith.cmpi slt, %505, %507 : i64
cf.cond_br %508, ^bb88, ^bb89
^bb88:
%509 = llvm.load %504 : !llvm.ptr -> i64
%510 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%511 = arith.subi %509, %512 : i64
%513 = arith.remsi %511, %386 : i64
%514 = arith.muli %472, %513 : i64
%515 = arith.remsi %514, %386 : i64
%516 = arith.constant 0 : i32
%518 = arith.extsi %516 : i32 to i64
%517 = arith.cmpi eq, %515, %518 : i64
cf.cond_br %517, ^bb90, ^bb91
^bb90:
%519 = arith.trunci %386 : i64 to i32
%520 = llvm.load %504 : !llvm.ptr -> i64
%521 = arith.subi %520, %492 : i64
%522 = arith.addi %501, %521 : i64
%523 = llvm.getelementptr %454[%522] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %519, %523 : i32, !llvm.ptr
cf.br ^bb92
^bb91:
%524 = arith.trunci %515 : i64 to i32
%525 = llvm.load %504 : !llvm.ptr -> i64
%526 = arith.subi %525, %492 : i64
%527 = arith.addi %501, %526 : i64
%528 = llvm.getelementptr %454[%527] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %524, %528 : i32, !llvm.ptr
cf.br ^bb92
^bb92:
%529 = llvm.load %504 : !llvm.ptr -> i64
%530 = arith.constant 1 : i32
%532 = arith.extsi %530 : i32 to i64
%531 = arith.addi %529, %532 : i64
llvm.store %531, %504 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%533 = arith.constant 0 : i32
%534 = arith.extsi %533 : i32 to i64
%535 = llvm.mlir.constant(1 : i64) : i64
%536 = llvm.alloca %535 x i64 : (i64) -> !llvm.ptr
llvm.store %534, %536 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%537 = llvm.load %536 : !llvm.ptr -> i64
%538 = llvm.load %479 : !llvm.ptr -> i64
%539 = arith.cmpi slt, %537, %538 : i64
cf.cond_br %539, ^bb94, ^bb95
^bb94:
%541 = llvm.load %536 : !llvm.ptr -> i64
%542 = arith.addi %501, %541 : i64
%543 = llvm.getelementptr %454[%542] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%540 = llvm.load %543 : !llvm.ptr -> i32
%544 = arith.extsi %540 : i32 to i64
%545 = llvm.load %479 : !llvm.ptr -> i64
%546 = arith.trunci %545 : i64 to i32
%547 = llvm.getelementptr %460[%544] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %546, %547 : i32, !llvm.ptr
%548 = llvm.load %536 : !llvm.ptr -> i64
%549 = arith.trunci %548 : i64 to i32
%550 = llvm.getelementptr %466[%544] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %549, %550 : i32, !llvm.ptr
%551 = llvm.load %536 : !llvm.ptr -> i64
%552 = arith.constant 1 : i32
%554 = arith.extsi %552 : i32 to i64
%553 = arith.addi %551, %554 : i64
llvm.store %553, %536 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%555 = llvm.load %479 : !llvm.ptr -> i64
%556 = arith.constant 1 : i32
%558 = arith.extsi %556 : i32 to i64
%557 = arith.addi %555, %558 : i64
llvm.store %557, %479 : i64, !llvm.ptr
cf.br ^bb84
^bb86:
%559 = func.call @lcm_upto_mod(%380) : (i64) -> i64
%561 = llvm.mlir.addressof @MM : !llvm.ptr
%562 = llvm.load %561 : !llvm.ptr -> i64
%563 = arith.constant 1 : i32
%565 = arith.extsi %563 : i32 to i64
%564 = arith.addi %562, %565 : i64
%566 = llvm.mlir.addressof @MM : !llvm.ptr
%567 = llvm.load %566 : !llvm.ptr -> i64
%568 = arith.constant 1 : i32
%570 = arith.extsi %568 : i32 to i64
%569 = arith.addi %567, %570 : i64
%571 = arith.muli %564, %569 : i64
%572 = arith.constant 8 : i32
%573 = arith.extsi %572 : i32 to i64
%560 = func.call @calloc(%571, %573) : (i64, i64) -> !llvm.ptr
%575 = llvm.mlir.addressof @MM : !llvm.ptr
%576 = llvm.load %575 : !llvm.ptr -> i64
%577 = arith.constant 1 : i32
%579 = arith.extsi %577 : i32 to i64
%578 = arith.addi %576, %579 : i64
%580 = llvm.mlir.addressof @MM : !llvm.ptr
%581 = llvm.load %580 : !llvm.ptr -> i64
%582 = arith.constant 1 : i32
%584 = arith.extsi %582 : i32 to i64
%583 = arith.addi %581, %584 : i64
%585 = arith.muli %578, %583 : i64
%586 = arith.constant 8 : i32
%587 = arith.extsi %586 : i32 to i64
%574 = func.call @calloc(%585, %587) : (i64, i64) -> !llvm.ptr
%589 = llvm.mlir.addressof @MM : !llvm.ptr
%590 = llvm.load %589 : !llvm.ptr -> i64
%591 = arith.constant 1 : i32
%593 = arith.extsi %591 : i32 to i64
%592 = arith.addi %590, %593 : i64
%594 = llvm.mlir.addressof @MM : !llvm.ptr
%595 = llvm.load %594 : !llvm.ptr -> i64
%596 = arith.constant 1 : i32
%598 = arith.extsi %596 : i32 to i64
%597 = arith.addi %595, %598 : i64
%599 = arith.muli %592, %597 : i64
%600 = llvm.mlir.addressof @MM : !llvm.ptr
%601 = llvm.load %600 : !llvm.ptr -> i64
%602 = arith.muli %599, %601 : i64
%603 = arith.constant 4 : i32
%604 = arith.extsi %603 : i32 to i64
%588 = func.call @calloc(%602, %604) : (i64, i64) -> !llvm.ptr
%606 = llvm.mlir.addressof @MM : !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.constant 4 : i32
%612 = arith.extsi %611 : i32 to i64
%605 = func.call @calloc(%609, %612) : (i64, i64) -> !llvm.ptr
%614 = llvm.mlir.addressof @MM : !llvm.ptr
%615 = llvm.load %614 : !llvm.ptr -> i64
%616 = arith.constant 1 : i32
%618 = arith.extsi %616 : i32 to i64
%617 = arith.addi %615, %618 : i64
%619 = arith.constant 4 : i32
%620 = arith.extsi %619 : i32 to i64
%613 = func.call @calloc(%617, %620) : (i64, i64) -> !llvm.ptr
%622 = llvm.mlir.addressof @MM : !llvm.ptr
%623 = llvm.load %622 : !llvm.ptr -> i64
%624 = arith.constant 1 : i32
%626 = arith.extsi %624 : i32 to i64
%625 = arith.addi %623, %626 : i64
%627 = arith.constant 8 : i32
%628 = arith.extsi %627 : i32 to i64
%621 = func.call @calloc(%625, %628) : (i64, i64) -> !llvm.ptr
%630 = llvm.mlir.addressof @MM : !llvm.ptr
%631 = llvm.load %630 : !llvm.ptr -> i64
%632 = arith.constant 1 : i32
%634 = arith.extsi %632 : i32 to i64
%633 = arith.addi %631, %634 : i64
%635 = arith.constant 8 : i32
%636 = arith.extsi %635 : i32 to i64
%629 = func.call @calloc(%633, %636) : (i64, i64) -> !llvm.ptr
%638 = llvm.mlir.addressof @MM : !llvm.ptr
%639 = llvm.load %638 : !llvm.ptr -> i64
%640 = arith.constant 1 : i32
%642 = arith.extsi %640 : i32 to i64
%641 = arith.addi %639, %642 : i64
%643 = arith.constant 8 : i32
%644 = arith.extsi %643 : i32 to i64
%637 = func.call @calloc(%641, %644) : (i64, i64) -> !llvm.ptr
%646 = llvm.mlir.addressof @MM : !llvm.ptr
%647 = llvm.load %646 : !llvm.ptr -> i64
%648 = arith.constant 1 : i32
%650 = arith.extsi %648 : i32 to i64
%649 = arith.addi %647, %650 : i64
%651 = arith.constant 8 : i32
%652 = arith.extsi %651 : i32 to i64
%645 = func.call @calloc(%649, %652) : (i64, i64) -> !llvm.ptr
%653 = arith.constant 1 : i32
%654 = arith.extsi %653 : i32 to i64
%655 = llvm.mlir.constant(1 : i64) : i64
%656 = llvm.alloca %655 x i64 : (i64) -> !llvm.ptr
llvm.store %654, %656 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%657 = llvm.load %656 : !llvm.ptr -> i64
%658 = arith.cmpi sle, %657, %380 : i64
cf.cond_br %658, ^bb97, ^bb98
^bb97:
%659 = llvm.load %656 : !llvm.ptr -> i64
%660 = llvm.load %656 : !llvm.ptr -> i64
%661 = arith.constant 1 : i32
%663 = arith.extsi %661 : i32 to i64
%662 = arith.subi %660, %663 : i64
%664 = arith.muli %659, %662 : i64
%665 = arith.constant 2 : i32
%667 = arith.extsi %665 : i32 to i64
%666 = arith.divsi %664, %667 : i64
%668 = arith.constant 1 : i32
%669 = arith.extsi %668 : i32 to i64
%670 = llvm.mlir.constant(1 : i64) : i64
%671 = llvm.alloca %670 x i64 : (i64) -> !llvm.ptr
llvm.store %669, %671 : i64, !llvm.ptr
cf.br ^bb99
^bb99:
%672 = llvm.load %671 : !llvm.ptr -> i64
%673 = arith.cmpi sle, %672, %380 : i64
cf.cond_br %673, ^bb100, ^bb101
^bb100:
%675 = llvm.load %656 : !llvm.ptr -> i64
%676 = llvm.load %671 : !llvm.ptr -> i64
%674 = func.call @gcd(%675, %676) : (i64, i64) -> i64
%677 = llvm.load %656 : !llvm.ptr -> i64
%678 = llvm.mlir.addressof @MM : !llvm.ptr
%679 = llvm.load %678 : !llvm.ptr -> i64
%680 = arith.constant 1 : i32
%682 = arith.extsi %680 : i32 to i64
%681 = arith.addi %679, %682 : i64
%683 = arith.muli %677, %681 : i64
%684 = llvm.load %671 : !llvm.ptr -> i64
%685 = arith.addi %683, %684 : i64
%686 = llvm.getelementptr %560[%685] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %674, %686 : i64, !llvm.ptr
%687 = llvm.load %656 : !llvm.ptr -> i64
%688 = arith.divsi %687, %674 : i64
%689 = llvm.load %671 : !llvm.ptr -> i64
%690 = arith.muli %688, %689 : i64
%692 = llvm.mlir.addressof @MOD : !llvm.ptr
%693 = llvm.load %692 : !llvm.ptr -> i64
%694 = arith.remsi %690, %693 : i64
%695 = llvm.mlir.addressof @MOD : !llvm.ptr
%696 = llvm.load %695 : !llvm.ptr -> i64
%697 = arith.constant 2 : i32
%699 = arith.extsi %697 : i32 to i64
%698 = arith.subi %696, %699 : i64
%700 = llvm.mlir.addressof @MOD : !llvm.ptr
%701 = llvm.load %700 : !llvm.ptr -> i64
%691 = func.call @mod_pow(%694, %698, %701) : (i64, i64, i64) -> i64
%702 = arith.muli %559, %691 : i64
%703 = llvm.mlir.addressof @MOD : !llvm.ptr
%704 = llvm.load %703 : !llvm.ptr -> i64
%705 = arith.remsi %702, %704 : i64
%706 = llvm.load %656 : !llvm.ptr -> i64
%707 = llvm.mlir.addressof @MM : !llvm.ptr
%708 = llvm.load %707 : !llvm.ptr -> i64
%709 = arith.constant 1 : i32
%711 = arith.extsi %709 : i32 to i64
%710 = arith.addi %708, %711 : i64
%712 = arith.muli %706, %710 : i64
%713 = llvm.load %671 : !llvm.ptr -> i64
%714 = arith.addi %712, %713 : i64
%715 = llvm.getelementptr %574[%714] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %705, %715 : i64, !llvm.ptr
%716 = llvm.load %671 : !llvm.ptr -> i64
%717 = llvm.load %671 : !llvm.ptr -> i64
%718 = arith.constant 1 : i32
%720 = arith.extsi %718 : i32 to i64
%719 = arith.subi %717, %720 : i64
%721 = arith.muli %716, %719 : i64
%722 = arith.constant 2 : i32
%724 = arith.extsi %722 : i32 to i64
%723 = arith.divsi %721, %724 : i64
%725 = arith.constant 0 : i32
%726 = arith.extsi %725 : i32 to i64
%727 = llvm.mlir.constant(1 : i64) : i64
%728 = llvm.alloca %727 x i64 : (i64) -> !llvm.ptr
llvm.store %726, %728 : i64, !llvm.ptr
%729 = arith.constant 0 : i32
%730 = arith.extsi %729 : i32 to i64
%731 = llvm.mlir.constant(1 : i64) : i64
%732 = llvm.alloca %731 x i64 : (i64) -> !llvm.ptr
llvm.store %730, %732 : i64, !llvm.ptr
%733 = arith.constant 0 : i32
%734 = arith.extsi %733 : i32 to i64
%735 = llvm.mlir.constant(1 : i64) : i64
%736 = llvm.alloca %735 x i64 : (i64) -> !llvm.ptr
llvm.store %734, %736 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%737 = llvm.load %736 : !llvm.ptr -> i64
%738 = arith.cmpi slt, %737, %674 : i64
cf.cond_br %738, ^bb103, ^bb104
^bb103:
%739 = llvm.load %728 : !llvm.ptr -> i64
%740 = llvm.load %736 : !llvm.ptr -> i64
%741 = llvm.getelementptr %621[%740] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %739, %741 : i64, !llvm.ptr
%742 = llvm.load %656 : !llvm.ptr -> i64
%743 = llvm.load %736 : !llvm.ptr -> i64
%744 = arith.subi %742, %743 : i64
%745 = arith.addi %744, %674 : i64
%746 = arith.constant 1 : i32
%748 = arith.extsi %746 : i32 to i64
%747 = arith.subi %745, %748 : i64
%749 = arith.divsi %747, %674 : i64
%750 = llvm.mlir.constant(1 : i64) : i64
%751 = llvm.alloca %750 x i64 : (i64) -> !llvm.ptr
llvm.store %749, %751 : i64, !llvm.ptr
%752 = llvm.load %736 : !llvm.ptr -> i64
%753 = llvm.load %656 : !llvm.ptr -> i64
%754 = arith.cmpi sge, %752, %753 : i64
cf.cond_br %754, ^bb105, ^bb106
^bb105:
%755 = arith.constant 0 : i32
%756 = arith.extsi %755 : i32 to i64
llvm.store %756, %751 : i64, !llvm.ptr
cf.br ^bb107
^bb106:
cf.br ^bb107
^bb107:
%757 = llvm.load %751 : !llvm.ptr -> i64
%758 = llvm.load %736 : !llvm.ptr -> i64
%759 = llvm.getelementptr %637[%758] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %757, %759 : i64, !llvm.ptr
%760 = llvm.load %728 : !llvm.ptr -> i64
%761 = llvm.load %751 : !llvm.ptr -> i64
%762 = arith.addi %760, %761 : i64
llvm.store %762, %728 : i64, !llvm.ptr
%763 = llvm.load %732 : !llvm.ptr -> i64
%764 = llvm.load %736 : !llvm.ptr -> i64
%765 = llvm.getelementptr %629[%764] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %763, %765 : i64, !llvm.ptr
%766 = llvm.load %671 : !llvm.ptr -> i64
%767 = llvm.load %736 : !llvm.ptr -> i64
%768 = arith.subi %766, %767 : i64
%769 = arith.addi %768, %674 : i64
%770 = arith.constant 1 : i32
%772 = arith.extsi %770 : i32 to i64
%771 = arith.subi %769, %772 : i64
%773 = arith.divsi %771, %674 : i64
%774 = llvm.mlir.constant(1 : i64) : i64
%775 = llvm.alloca %774 x i64 : (i64) -> !llvm.ptr
llvm.store %773, %775 : i64, !llvm.ptr
%776 = llvm.load %736 : !llvm.ptr -> i64
%777 = llvm.load %671 : !llvm.ptr -> i64
%778 = arith.cmpi sge, %776, %777 : i64
cf.cond_br %778, ^bb108, ^bb109
^bb108:
%779 = arith.constant 0 : i32
%780 = arith.extsi %779 : i32 to i64
llvm.store %780, %775 : i64, !llvm.ptr
cf.br ^bb110
^bb109:
cf.br ^bb110
^bb110:
%781 = llvm.load %775 : !llvm.ptr -> i64
%782 = llvm.load %736 : !llvm.ptr -> i64
%783 = llvm.getelementptr %645[%782] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %781, %783 : i64, !llvm.ptr
%784 = llvm.load %732 : !llvm.ptr -> i64
%785 = llvm.load %775 : !llvm.ptr -> i64
%786 = arith.addi %784, %785 : i64
llvm.store %786, %732 : i64, !llvm.ptr
%787 = llvm.load %736 : !llvm.ptr -> i64
%788 = arith.constant 1 : i32
%790 = arith.extsi %788 : i32 to i64
%789 = arith.addi %787, %790 : i64
llvm.store %789, %736 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%791 = arith.constant 0 : i32
%792 = arith.extsi %791 : i32 to i64
llvm.store %792, %736 : i64, !llvm.ptr
cf.br ^bb111
^bb111:
%793 = llvm.load %736 : !llvm.ptr -> i64
%794 = arith.cmpi slt, %793, %674 : i64
cf.cond_br %794, ^bb112, ^bb113
^bb112:
%795 = arith.constant 0 : i32
%796 = arith.extsi %795 : i32 to i64
%797 = llvm.mlir.constant(1 : i64) : i64
%798 = llvm.alloca %797 x i64 : (i64) -> !llvm.ptr
llvm.store %796, %798 : i64, !llvm.ptr
%799 = llvm.load %736 : !llvm.ptr -> i64
%800 = llvm.mlir.constant(1 : i64) : i64
%801 = llvm.alloca %800 x i64 : (i64) -> !llvm.ptr
llvm.store %799, %801 : i64, !llvm.ptr
cf.br ^bb114
^bb114:
%802 = llvm.load %801 : !llvm.ptr -> i64
%803 = llvm.load %656 : !llvm.ptr -> i64
%804 = arith.cmpi slt, %802, %803 : i64
cf.cond_br %804, ^bb115, ^bb116
^bb115:
%806 = llvm.load %801 : !llvm.ptr -> i64
%807 = arith.addi %666, %806 : i64
%808 = llvm.getelementptr %454[%807] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%805 = llvm.load %808 : !llvm.ptr -> i32
%810 = llvm.load %736 : !llvm.ptr -> i64
%811 = llvm.getelementptr %621[%810] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%809 = llvm.load %811 : !llvm.ptr -> i64
%812 = llvm.load %798 : !llvm.ptr -> i64
%813 = arith.addi %809, %812 : i64
%814 = llvm.getelementptr %605[%813] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %805, %814 : i32, !llvm.ptr
%815 = llvm.load %798 : !llvm.ptr -> i64
%816 = arith.constant 1 : i32
%818 = arith.extsi %816 : i32 to i64
%817 = arith.addi %815, %818 : i64
llvm.store %817, %798 : i64, !llvm.ptr
%819 = llvm.load %801 : !llvm.ptr -> i64
%820 = arith.addi %819, %674 : i64
llvm.store %820, %801 : i64, !llvm.ptr
cf.br ^bb114
^bb116:
%821 = arith.constant 0 : i32
%822 = arith.extsi %821 : i32 to i64
llvm.store %822, %798 : i64, !llvm.ptr
%823 = llvm.load %736 : !llvm.ptr -> i64
llvm.store %823, %801 : i64, !llvm.ptr
cf.br ^bb117
^bb117:
%824 = llvm.load %801 : !llvm.ptr -> i64
%825 = llvm.load %671 : !llvm.ptr -> i64
%826 = arith.cmpi slt, %824, %825 : i64
cf.cond_br %826, ^bb118, ^bb119
^bb118:
%828 = llvm.load %801 : !llvm.ptr -> i64
%829 = arith.addi %723, %828 : i64
%830 = llvm.getelementptr %454[%829] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%827 = llvm.load %830 : !llvm.ptr -> i32
%832 = llvm.load %736 : !llvm.ptr -> i64
%833 = llvm.getelementptr %629[%832] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%831 = llvm.load %833 : !llvm.ptr -> i64
%834 = llvm.load %798 : !llvm.ptr -> i64
%835 = arith.addi %831, %834 : i64
%836 = llvm.getelementptr %613[%835] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %827, %836 : i32, !llvm.ptr
%837 = llvm.load %798 : !llvm.ptr -> i64
%838 = arith.constant 1 : i32
%840 = arith.extsi %838 : i32 to i64
%839 = arith.addi %837, %840 : i64
llvm.store %839, %798 : i64, !llvm.ptr
%841 = llvm.load %801 : !llvm.ptr -> i64
%842 = arith.addi %841, %674 : i64
llvm.store %842, %801 : i64, !llvm.ptr
cf.br ^bb117
^bb119:
%845 = llvm.load %736 : !llvm.ptr -> i64
%846 = llvm.getelementptr %629[%845] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%844 = llvm.load %846 : !llvm.ptr -> i64
%848 = llvm.load %736 : !llvm.ptr -> i64
%849 = llvm.getelementptr %645[%848] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%847 = llvm.load %849 : !llvm.ptr -> i64
func.call @sort_sub(%613, %844, %847) : (!llvm.ptr, i64, i64) -> ()
%850 = llvm.load %736 : !llvm.ptr -> i64
%851 = arith.constant 1 : i32
%853 = arith.extsi %851 : i32 to i64
%852 = arith.addi %850, %853 : i64
llvm.store %852, %736 : i64, !llvm.ptr
cf.br ^bb111
^bb113:
%854 = arith.constant 0 : i32
%855 = arith.extsi %854 : i32 to i64
%856 = llvm.mlir.constant(1 : i64) : i64
%857 = llvm.alloca %856 x i64 : (i64) -> !llvm.ptr
llvm.store %855, %857 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%858 = llvm.load %857 : !llvm.ptr -> i64
%859 = arith.cmpi slt, %858, %674 : i64
cf.cond_br %859, ^bb121, ^bb122
^bb121:
%860 = arith.constant 0 : i32
%861 = arith.extsi %860 : i32 to i64
%862 = llvm.mlir.constant(1 : i64) : i64
%863 = llvm.alloca %862 x i64 : (i64) -> !llvm.ptr
llvm.store %861, %863 : i64, !llvm.ptr
%864 = arith.constant 0 : i32
%865 = arith.extsi %864 : i32 to i64
llvm.store %865, %736 : i64, !llvm.ptr
cf.br ^bb123
^bb123:
%866 = llvm.load %736 : !llvm.ptr -> i64
%867 = arith.cmpi slt, %866, %674 : i64
cf.cond_br %867, ^bb124, ^bb125
^bb124:
%868 = llvm.load %736 : !llvm.ptr -> i64
%869 = llvm.load %857 : !llvm.ptr -> i64
%870 = arith.subi %868, %869 : i64
%871 = arith.remsi %870, %674 : i64
%872 = arith.addi %871, %674 : i64
%873 = arith.remsi %872, %674 : i64
%875 = llvm.getelementptr %629[%873] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%874 = llvm.load %875 : !llvm.ptr -> i64
%877 = llvm.getelementptr %645[%873] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%876 = llvm.load %877 : !llvm.ptr -> i64
%878 = arith.constant 0 : i32
%879 = arith.extsi %878 : i32 to i64
%880 = llvm.mlir.constant(1 : i64) : i64
%881 = llvm.alloca %880 x i64 : (i64) -> !llvm.ptr
llvm.store %879, %881 : i64, !llvm.ptr
cf.br ^bb126
^bb126:
%882 = llvm.load %881 : !llvm.ptr -> i64
%884 = llvm.load %736 : !llvm.ptr -> i64
%885 = llvm.getelementptr %637[%884] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%883 = llvm.load %885 : !llvm.ptr -> i64
%886 = arith.cmpi slt, %882, %883 : i64
cf.cond_br %886, ^bb127, ^bb128
^bb127:
%889 = llvm.load %736 : !llvm.ptr -> i64
%890 = llvm.getelementptr %621[%889] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%888 = llvm.load %890 : !llvm.ptr -> i64
%891 = llvm.load %881 : !llvm.ptr -> i64
%892 = arith.addi %888, %891 : i64
%893 = llvm.getelementptr %605[%892] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%887 = llvm.load %893 : !llvm.ptr -> i32
%894 = llvm.load %863 : !llvm.ptr -> i64
%895 = func.call @lower_bound_sub(%613, %874, %876, %887) : (!llvm.ptr, i64, i64, i32) -> i64
%896 = arith.addi %894, %895 : i64
llvm.store %896, %863 : i64, !llvm.ptr
%897 = llvm.load %881 : !llvm.ptr -> i64
%898 = arith.constant 1 : i32
%900 = arith.extsi %898 : i32 to i64
%899 = arith.addi %897, %900 : i64
llvm.store %899, %881 : i64, !llvm.ptr
cf.br ^bb126
^bb128:
%901 = llvm.load %736 : !llvm.ptr -> i64
%902 = arith.constant 1 : i32
%904 = arith.extsi %902 : i32 to i64
%903 = arith.addi %901, %904 : i64
llvm.store %903, %736 : i64, !llvm.ptr
cf.br ^bb123
^bb125:
%905 = llvm.load %863 : !llvm.ptr -> i64
%906 = arith.trunci %905 : i64 to i32
%907 = llvm.load %656 : !llvm.ptr -> i64
%908 = llvm.mlir.addressof @MM : !llvm.ptr
%909 = llvm.load %908 : !llvm.ptr -> i64
%910 = arith.constant 1 : i32
%912 = arith.extsi %910 : i32 to i64
%911 = arith.addi %909, %912 : i64
%913 = arith.muli %907, %911 : i64
%914 = llvm.mlir.addressof @MM : !llvm.ptr
%915 = llvm.load %914 : !llvm.ptr -> i64
%916 = arith.muli %913, %915 : i64
%917 = llvm.load %671 : !llvm.ptr -> i64
%918 = llvm.mlir.addressof @MM : !llvm.ptr
%919 = llvm.load %918 : !llvm.ptr -> i64
%920 = arith.muli %917, %919 : i64
%921 = arith.addi %916, %920 : i64
%922 = llvm.load %857 : !llvm.ptr -> i64
%923 = arith.addi %921, %922 : i64
%924 = llvm.getelementptr %588[%923] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %906, %924 : i32, !llvm.ptr
%925 = llvm.load %857 : !llvm.ptr -> i64
%926 = arith.constant 1 : i32
%928 = arith.extsi %926 : i32 to i64
%927 = arith.addi %925, %928 : i64
llvm.store %927, %857 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%929 = llvm.load %671 : !llvm.ptr -> i64
%930 = arith.constant 1 : i32
%932 = arith.extsi %930 : i32 to i64
%931 = arith.addi %929, %932 : i64
llvm.store %931, %671 : i64, !llvm.ptr
cf.br ^bb99
^bb101:
%933 = llvm.load %656 : !llvm.ptr -> i64
%934 = arith.constant 1 : i32
%936 = arith.extsi %934 : i32 to i64
%935 = arith.addi %933, %936 : i64
llvm.store %935, %656 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
func.call @free(%605) : (!llvm.ptr) -> ()
func.call @free(%613) : (!llvm.ptr) -> ()
func.call @free(%621) : (!llvm.ptr) -> ()
func.call @free(%629) : (!llvm.ptr) -> ()
func.call @free(%637) : (!llvm.ptr) -> ()
func.call @free(%645) : (!llvm.ptr) -> ()
%943 = arith.constant 0 : i32
%944 = arith.extsi %943 : i32 to i64
%945 = llvm.mlir.constant(1 : i64) : i64
%946 = llvm.alloca %945 x i64 : (i64) -> !llvm.ptr
llvm.store %944, %946 : i64, !llvm.ptr
%947 = arith.constant 1 : i32
%948 = arith.extsi %947 : i32 to i64
llvm.store %948, %407 : i64, !llvm.ptr
cf.br ^bb129
^bb129:
%949 = llvm.load %407 : !llvm.ptr -> i64
%950 = arith.cmpi slt, %949, %386 : i64
cf.cond_br %950, ^bb130, ^bb131
^bb130:
%952 = llvm.load %407 : !llvm.ptr -> i64
%953 = llvm.getelementptr %427[%952] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%951 = llvm.load %953 : !llvm.ptr -> i64
%955 = llvm.load %407 : !llvm.ptr -> i64
%956 = llvm.getelementptr %460[%955] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%954 = llvm.load %956 : !llvm.ptr -> i32
%957 = arith.extsi %954 : i32 to i64
%959 = llvm.load %407 : !llvm.ptr -> i64
%960 = llvm.getelementptr %466[%959] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%958 = llvm.load %960 : !llvm.ptr -> i32
%961 = arith.extsi %958 : i32 to i64
%962 = llvm.load %407 : !llvm.ptr -> i64
%963 = arith.constant 1 : i32
%965 = arith.extsi %963 : i32 to i64
%964 = arith.addi %962, %965 : i64
%966 = llvm.mlir.constant(1 : i64) : i64
%967 = llvm.alloca %966 x i64 : (i64) -> !llvm.ptr
llvm.store %964, %967 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%968 = llvm.load %967 : !llvm.ptr -> i64
%969 = arith.cmpi sle, %968, %386 : i64
cf.cond_br %969, ^bb133, ^bb134
^bb133:
%971 = llvm.load %967 : !llvm.ptr -> i64
%972 = llvm.getelementptr %460[%971] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%970 = llvm.load %972 : !llvm.ptr -> i32
%973 = arith.extsi %970 : i32 to i64
%975 = llvm.mlir.addressof @MM : !llvm.ptr
%976 = llvm.load %975 : !llvm.ptr -> i64
%977 = arith.constant 1 : i32
%979 = arith.extsi %977 : i32 to i64
%978 = arith.addi %976, %979 : i64
%980 = arith.muli %957, %978 : i64
%981 = arith.addi %980, %973 : i64
%982 = llvm.getelementptr %560[%981] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%974 = llvm.load %982 : !llvm.ptr -> i64
%983 = arith.constant 0 : i32
%984 = arith.extsi %983 : i32 to i64
%985 = llvm.mlir.constant(1 : i64) : i64
%986 = llvm.alloca %985 x i64 : (i64) -> !llvm.ptr
llvm.store %984, %986 : i64, !llvm.ptr
%987 = arith.constant 1 : i32
%989 = arith.extsi %987 : i32 to i64
%988 = arith.cmpi eq, %974, %989 : i64
cf.cond_br %988, ^bb135, ^bb136
^bb135:
%990 = arith.constant 0 : i32
%991 = arith.extsi %990 : i32 to i64
llvm.store %991, %986 : i64, !llvm.ptr
cf.br ^bb137
^bb136:
%993 = llvm.load %967 : !llvm.ptr -> i64
%994 = llvm.getelementptr %466[%993] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%992 = llvm.load %994 : !llvm.ptr -> i32
%995 = arith.extsi %992 : i32 to i64
%996 = arith.subi %961, %995 : i64
%997 = arith.remsi %996, %974 : i64
%998 = arith.addi %997, %974 : i64
%999 = arith.remsi %998, %974 : i64
llvm.store %999, %986 : i64, !llvm.ptr
cf.br ^bb137
^bb137:
%1001 = llvm.mlir.addressof @MM : !llvm.ptr
%1002 = llvm.load %1001 : !llvm.ptr -> i64
%1003 = arith.constant 1 : i32
%1005 = arith.extsi %1003 : i32 to i64
%1004 = arith.addi %1002, %1005 : i64
%1006 = arith.muli %957, %1004 : i64
%1007 = llvm.mlir.addressof @MM : !llvm.ptr
%1008 = llvm.load %1007 : !llvm.ptr -> i64
%1009 = arith.muli %1006, %1008 : i64
%1010 = llvm.mlir.addressof @MM : !llvm.ptr
%1011 = llvm.load %1010 : !llvm.ptr -> i64
%1012 = arith.muli %973, %1011 : i64
%1013 = arith.addi %1009, %1012 : i64
%1014 = llvm.load %986 : !llvm.ptr -> i64
%1015 = arith.addi %1013, %1014 : i64
%1016 = llvm.getelementptr %588[%1015] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%1000 = llvm.load %1016 : !llvm.ptr -> i32
%1017 = arith.extsi %1000 : i32 to i64
%1018 = arith.constant 0 : i32
%1020 = arith.extsi %1018 : i32 to i64
%1019 = arith.cmpi ne, %1017, %1020 : i64
cf.cond_br %1019, ^bb138, ^bb139
^bb138:
%1022 = llvm.mlir.addressof @MM : !llvm.ptr
%1023 = llvm.load %1022 : !llvm.ptr -> i64
%1024 = arith.constant 1 : i32
%1026 = arith.extsi %1024 : i32 to i64
%1025 = arith.addi %1023, %1026 : i64
%1027 = arith.muli %957, %1025 : i64
%1028 = arith.addi %1027, %973 : i64
%1029 = llvm.getelementptr %574[%1028] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1021 = llvm.load %1029 : !llvm.ptr -> i64
%1030 = arith.muli %1021, %1017 : i64
%1031 = llvm.mlir.addressof @MOD : !llvm.ptr
%1032 = llvm.load %1031 : !llvm.ptr -> i64
%1033 = arith.remsi %1030, %1032 : i64
%1034 = llvm.load %946 : !llvm.ptr -> i64
%1035 = arith.muli %951, %1033 : i64
%1036 = arith.addi %1034, %1035 : i64
llvm.store %1036, %946 : i64, !llvm.ptr
%1037 = llvm.load %946 : !llvm.ptr -> i64
%1038 = arith.constant 4611686014132420608 : i32
%1040 = arith.extsi %1038 : i32 to i64
%1039 = arith.cmpi sge, %1037, %1040 : i64
cf.cond_br %1039, ^bb141, ^bb142
^bb141:
%1041 = llvm.load %946 : !llvm.ptr -> i64
%1042 = llvm.mlir.addressof @MOD : !llvm.ptr
%1043 = llvm.load %1042 : !llvm.ptr -> i64
%1044 = arith.remsi %1041, %1043 : i64
llvm.store %1044, %946 : i64, !llvm.ptr
cf.br ^bb143
^bb142:
cf.br ^bb143
^bb143:
cf.br ^bb140
^bb139:
cf.br ^bb140
^bb140:
%1045 = llvm.load %967 : !llvm.ptr -> i64
%1046 = arith.constant 1 : i32
%1048 = arith.extsi %1046 : i32 to i64
%1047 = arith.addi %1045, %1048 : i64
llvm.store %1047, %967 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%1049 = llvm.load %407 : !llvm.ptr -> i64
%1050 = arith.constant 1 : i32
%1052 = arith.extsi %1050 : i32 to i64
%1051 = arith.addi %1049, %1052 : i64
llvm.store %1051, %407 : i64, !llvm.ptr
cf.br ^bb129
^bb131:
%1053 = llvm.load %946 : !llvm.ptr -> i64
%1054 = llvm.mlir.addressof @MOD : !llvm.ptr
%1055 = llvm.load %1054 : !llvm.ptr -> i64
%1056 = arith.remsi %1053, %1055 : i64
llvm.store %1056, %946 : i64, !llvm.ptr
%1057 = llvm.load %946 : !llvm.ptr -> i64
%1058 = arith.addi %559, %1057 : i64
%1059 = llvm.mlir.addressof @MOD : !llvm.ptr
%1060 = llvm.load %1059 : !llvm.ptr -> i64
%1061 = arith.remsi %1058, %1060 : i64
%1062 = arith.constant 1 : i32
%1063 = arith.extsi %1062 : i32 to i64
%1064 = llvm.mlir.constant(1 : i64) : i64
%1065 = llvm.alloca %1064 x i64 : (i64) -> !llvm.ptr
llvm.store %1063, %1065 : i64, !llvm.ptr
%1066 = arith.constant 2 : i32
%1067 = arith.extsi %1066 : i32 to i64
%1068 = llvm.mlir.constant(1 : i64) : i64
%1069 = llvm.alloca %1068 x i64 : (i64) -> !llvm.ptr
llvm.store %1067, %1069 : i64, !llvm.ptr
cf.br ^bb144
^bb144:
%1070 = llvm.load %1069 : !llvm.ptr -> i64
%1071 = arith.cmpi sle, %1070, %380 : i64
cf.cond_br %1071, ^bb145, ^bb146
^bb145:
%1072 = llvm.load %1065 : !llvm.ptr -> i64
%1073 = llvm.load %1069 : !llvm.ptr -> i64
%1074 = arith.muli %1072, %1073 : i64
%1075 = llvm.mlir.addressof @MOD : !llvm.ptr
%1076 = llvm.load %1075 : !llvm.ptr -> i64
%1077 = arith.remsi %1074, %1076 : i64
llvm.store %1077, %1065 : i64, !llvm.ptr
%1078 = llvm.load %1069 : !llvm.ptr -> i64
%1079 = arith.constant 1 : i32
%1081 = arith.extsi %1079 : i32 to i64
%1080 = arith.addi %1078, %1081 : i64
llvm.store %1080, %1069 : i64, !llvm.ptr
cf.br ^bb144
^bb146:
%1082 = llvm.load %1065 : !llvm.ptr -> i64
%1083 = arith.muli %1061, %1082 : i64
%1084 = llvm.mlir.addressof @MOD : !llvm.ptr
%1085 = llvm.load %1084 : !llvm.ptr -> i64
%1086 = arith.remsi %1083, %1085 : i64
%1088 = llvm.mlir.addressof @MOD : !llvm.ptr
%1089 = llvm.load %1088 : !llvm.ptr -> i64
%1090 = arith.constant 2 : i32
%1092 = arith.extsi %1090 : i32 to i64
%1091 = arith.subi %1089, %1092 : i64
%1093 = llvm.mlir.addressof @MOD : !llvm.ptr
%1094 = llvm.load %1093 : !llvm.ptr -> i64
%1087 = func.call @mod_pow(%559, %1091, %1094) : (i64, i64, i64) -> i64
%1095 = arith.muli %1086, %1087 : i64
%1096 = llvm.mlir.addressof @MOD : !llvm.ptr
%1097 = llvm.load %1096 : !llvm.ptr -> i64
%1098 = arith.remsi %1095, %1097 : i64
%1099 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1100 = llvm.call @printf(%1099, %1098) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%388) : (!llvm.ptr) -> ()
func.call @free(%427) : (!llvm.ptr) -> ()
func.call @free(%454) : (!llvm.ptr) -> ()
func.call @free(%460) : (!llvm.ptr) -> ()
func.call @free(%466) : (!llvm.ptr) -> ()
func.call @free(%560) : (!llvm.ptr) -> ()
func.call @free(%574) : (!llvm.ptr) -> ()
func.call @free(%588) : (!llvm.ptr) -> ()
%1109 = arith.constant 0 : i32
func.return %1109 : i32
}
}