← All problems Problem 1006
Fibonacci Subwords: Psi(10^18) mod 101001001. The k+1 distinct length-k factors of the Fibonacci word f = 010010100... are exactly the k+1 length-k windows of the two-sided word ... f2 f1 f0 1 | 0 f0 f1 f2 ... (window j covers [-j, k-1-j]) (rotation coding of x -> x + a on the circle, a = (3-sqrt5)/2; the k+1 breakpoints frac(-j*a) each start one distinct factor, and the factor started at frac(-j*a) reads c_{t-j} where c_t = floor((t+1)a) - floor(t*a), whose negative side mirrors f). Each window value splits into a left part (reversed f-prefix, digit weight 10^i) and a right part (f-prefix, digit weight 10^-i). Summing squares over j gives: * geometric-weighted sums of prefix values U_n = sum f_i 10^i and V_n = sum f_i 10^-i, plus their squares -- computed with O(log k) Fibonacci block merges; * one cross term sum_{a+b <= k-4} f_a f_b z^(a+b) for z = 10 and 10^-1, i.e. sums of z^(u+v) over pairs of upper-Wythoff numbers u+v <= k-2 (f_a = 1 iff a+1 = floor(n*phi^2)); a number is upper Wythoff iff its Zeckendorf representation ends at an odd Fibonacci index, so this is a digit DP over Fibonacci indices with an exact-budget state. Verified against brute force for k <= 20000 and Psi(3), Psi(10).
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)O(log n)Space complexity O(n^2)O(1)Approach Flow solution Matrix exponentiation Verdict Suboptimal
Flow source
# Project Euler 1006
# Fibonacci Subwords: Psi(10^18) mod 101001001.
#
# The k+1 distinct length-k factors of the Fibonacci word f = 010010100...
# are exactly the k+1 length-k windows of the two-sided word
# ... f2 f1 f0 1 | 0 f0 f1 f2 ... (window j covers [-j, k-1-j])
# (rotation coding of x -> x + a on the circle, a = (3-sqrt5)/2; the k+1
# breakpoints frac(-j*a) each start one distinct factor, and the factor
# started at frac(-j*a) reads c_{t-j} where c_t = floor((t+1)a) - floor(t*a),
# whose negative side mirrors f).
#
# Each window value splits into a left part (reversed f-prefix, digit weight
# 10^i) and a right part (f-prefix, digit weight 10^-i). Summing squares
# over j gives:
# * geometric-weighted sums of prefix values U_n = sum f_i 10^i and
# V_n = sum f_i 10^-i, plus their squares -- computed with O(log k)
# Fibonacci block merges;
# * one cross term sum_{a+b <= k-4} f_a f_b z^(a+b) for z = 10 and 10^-1,
# i.e. sums of z^(u+v) over pairs of upper-Wythoff numbers u+v <= k-2
# (f_a = 1 iff a+1 = floor(n*phi^2)); a number is upper Wythoff iff its
# Zeckendorf representation ends at an odd Fibonacci index, so this is
# a digit DP over Fibonacci indices with an exact-budget state.
# Verified against brute force for k <= 20000 and Psi(3), Psi(10).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const M: i64 = 101001001
const K: i64 = 1000000000000000000
function powmod(base: i64, exp: i64) -> i64 {
let mut result: i64 = 1
let mut b: i64 = base % M
let mut e: i64 = exp
while e > 0 {
if (e & 1) == 1 {
result = result * b % M
}
b = b * b % M
e = e >> 1
}
return result
}
# modular inverse via extended Euclid (M is not prime)
function inv_mod(a0: i64) -> i64 {
let mut g: i64 = M
let mut x: i64 = 0
let mut r: i64 = a0 % M
let mut s: i64 = 1
while r != 0 {
let q: i64 = g / r
let t: i64 = g - q * r
g = r
r = t
let u: i64 = x - q * s
x = s
s = u
}
x = x % M
if x < 0 {
x = x + M
}
return x
}
# Package for a 0/1 word w of length L with digit weight om^i, outer weight y:
# [0]=L [1]=om^L [2]=y^L [3]=S=sum w_i om^i
# [4]=T0=sum_{n<L} y^n [5]=T1=sum y^n U_n [6]=T2=sum y^n U_n^2
# where U_n = sum_{i<n} w_i om^i.
function pkg_merge(a: ptr<i64>, b: ptr<i64>, out: ptr<i64>) -> void {
let La: i64 = a[0]
let wA: i64 = a[1]
let yA: i64 = a[2]
let Sa: i64 = a[3]
let T0a: i64 = a[4]
let T1a: i64 = a[5]
let T2a: i64 = a[6]
let Lb: i64 = b[0]
let wB: i64 = b[1]
let yB: i64 = b[2]
let Sb: i64 = b[3]
let T0b: i64 = b[4]
let T1b: i64 = b[5]
let T2b: i64 = b[6]
out[0] = La + Lb
out[1] = wA * wB % M
out[2] = yA * yB % M
out[3] = (Sa + wA * Sb) % M
out[4] = (T0a + yA * T0b) % M
out[5] = (T1a + yA * ((Sa * T0b + wA * T1b) % M)) % M
let c1: i64 = Sa * Sa % M * T0b % M
let c2: i64 = 2 * Sa % M * wA % M * T1b % M
let c3: i64 = wA * wA % M * T2b % M
out[6] = (T2a + yA * ((c1 + c2 + c3) % M)) % M
}
function pkg_set(p: ptr<i64>, l: i64, w: i64, y: i64, s: i64, t0: i64, t1: i64, t2: i64) -> void {
p[0] = l
p[1] = w
p[2] = y
p[3] = s
p[4] = t0
p[5] = t1
p[6] = t2
}
function pkg_copy(dst: ptr<i64>, src: ptr<i64>) -> void {
let mut i: i64 = 0
while i < 7 {
dst[i] = src[i]
i = i + 1
}
}
# Package of the first N letters of the Fibonacci word (om, y as above).
# Blocks: b1 = "0", b2 = "01", bn = b_{n-1} b_{n-2}.
function f_prefix_pkg(N: i64, om: i64, y: i64, out: ptr<i64>) -> void {
let blk: ptr<i64> = calloc(96 * 7, 8)
pkg_set(blk + 1 * 7, 1, om, y, 0, 1, 0, 0)
let one: ptr<i64> = calloc(7, 8)
pkg_set(one, 1, om, y, 1, 1, 0, 0)
pkg_merge(blk + 1 * 7, one, blk + 2 * 7)
let mut top: i64 = 2
while blk[top * 7 + 0] < N {
top = top + 1
pkg_merge(blk + (top - 1) * 7, blk + (top - 2) * 7, blk + top * 7)
}
# acc = identity package (empty word)
let acc: ptr<i64> = calloc(7, 8)
let tmp: ptr<i64> = calloc(7, 8)
pkg_set(acc, 0, 1, 1, 0, 0, 0, 0)
let mut n: i64 = top
let mut rem: i64 = N
let mut done: i64 = 0
while done == 0 {
if rem == blk[n * 7 + 0] {
pkg_merge(acc, blk + n * 7, tmp)
pkg_copy(acc, tmp)
done = 1
} else {
if n <= 2 {
# rem < len(b2)=2, so rem == 1: single "0"
pkg_merge(acc, blk + 1 * 7, tmp)
pkg_copy(acc, tmp)
done = 1
} else {
if rem <= blk[(n - 1) * 7 + 0] {
n = n - 1
} else {
pkg_merge(acc, blk + (n - 1) * 7, tmp)
pkg_copy(acc, tmp)
rem = rem - blk[(n - 1) * 7 + 0]
n = n - 2
}
}
}
}
pkg_copy(out, acc)
free(blk)
free(one)
free(acc)
free(tmp)
}
# sum of z^(u+v) over pairs u, v of upper-Wythoff numbers with u + v <= X.
# Digit DP over Zeckendorf indices i = imax..2 (F[2]=1, F[3]=2, ...).
# State: exact budget R = X_{>=i} - u_{>=i} - v_{>=i} (or FREE once
# R >= 2(F_i - 1)), previous digit of u and v, and the parity class of the
# most recent 1 in u and v (0 none, 1 even index, 2 odd index); u, v are
# upper Wythoff iff their lowest 1 sits at an odd index.
function pair_sum(z: i64, X: i64) -> i64 {
if X < 4 {
return 0
}
let F: ptr<i64> = calloc(96, 8)
F[2] = 1
F[3] = 2
let mut nf: i64 = 3
while F[nf] < 4600000000000000000 {
nf = nf + 1
F[nf] = F[nf - 1] + F[nf - 2]
}
let mut imax: i64 = 2
while F[imax + 1] <= X {
imax = imax + 1
}
# Zeckendorf digits of X and running tails below each index
let xd: ptr<i64> = calloc(96, 8)
let mut remx: i64 = X
let mut i: i64 = imax
while i >= 2 {
if F[i] <= remx {
xd[i] = 1
remx = remx - F[i]
}
i = i - 1
}
let xtail: ptr<i64> = calloc(96, 8)
i = 3
while i <= imax {
xtail[i] = xtail[i - 1] + xd[i - 1] * F[i - 1]
i = i + 1
}
let zpow: ptr<i64> = calloc(96, 8)
i = 2
while i <= imax {
zpow[i] = powmod(z, F[i])
i = i + 1
}
# state arrays: code = ul + 2*vl + 4*up + 12*vp + 36*free (< 72)
let CAP: i64 = 512
let curR: ptr<i64> = calloc(CAP, 8)
let curC: ptr<i64> = calloc(CAP, 8)
let curV: ptr<i64> = calloc(CAP, 8)
let newR: ptr<i64> = calloc(CAP, 8)
let newC: ptr<i64> = calloc(CAP, 8)
let newV: ptr<i64> = calloc(CAP, 8)
let mut ncur: i64 = 1
curR[0] = 0
curC[0] = 0
curV[0] = 1
i = imax
while i >= 2 {
let xi: i64 = xd[i]
let fi: i64 = F[i]
let xt: i64 = xtail[i]
let zp: i64 = zpow[i]
let mut par: i64 = 1
if (i & 1) == 1 {
par = 2
}
let mut nnew: i64 = 0
let mut si: i64 = 0
while si < ncur {
let R: i64 = curR[si]
let code: i64 = curC[si]
let wgt: i64 = curV[si]
let fr: i64 = code / 36
let rest: i64 = code % 36
let vp: i64 = rest / 12
let up: i64 = rest % 12 / 4
let vl: i64 = rest % 4 / 2
let ul: i64 = rest % 2
let mut ui: i64 = 0
while ui < 2 {
if ui == 1 && ul == 1 {
ui = 2
} else {
let mut vi: i64 = 0
while vi < 2 {
if vi == 1 && vl == 1 {
vi = 2
} else {
let mut nR: i64 = 0
let mut nfr: i64 = fr
let mut dead: i64 = 0
if fr == 0 {
nR = R + (xi - ui - vi) * fi
if nR + xt < 0 {
dead = 1
}
if nR >= 2 * (fi - 1) {
nfr = 1
nR = 0
}
}
if dead == 0 {
let mut nup: i64 = up
if ui == 1 {
nup = par
}
let mut nvp: i64 = vp
if vi == 1 {
nvp = par
}
let mut w2: i64 = wgt
if ui + vi >= 1 {
w2 = w2 * zp % M
}
if ui + vi == 2 {
w2 = w2 * zp % M
}
let ncode: i64 = ui + 2 * vi + 4 * nup + 12 * nvp + 36 * nfr
# linear-search insert
let mut hit: i64 = 0 - 1
let mut t: i64 = 0
while t < nnew {
if newC[t] == ncode && newR[t] == nR {
hit = t
t = nnew
} else {
t = t + 1
}
}
if hit >= 0 {
newV[hit] = (newV[hit] + w2) % M
} else {
newR[nnew] = nR
newC[nnew] = ncode
newV[nnew] = w2
nnew = nnew + 1
}
}
vi = vi + 1
}
}
ui = ui + 1
}
}
si = si + 1
}
let mut t2: i64 = 0
while t2 < nnew {
curR[t2] = newR[t2]
curC[t2] = newC[t2]
curV[t2] = newV[t2]
t2 = t2 + 1
}
ncur = nnew
i = i - 1
}
let mut total: i64 = 0
let mut si2: i64 = 0
while si2 < ncur {
let code: i64 = curC[si2]
let fr: i64 = code / 36
let rest: i64 = code % 36
let vp: i64 = rest / 12
let up: i64 = rest % 12 / 4
if up == 2 && vp == 2 {
if fr == 1 || curR[si2] >= 0 {
total = (total + curV[si2]) % M
}
}
si2 = si2 + 1
}
free(F)
free(xd)
free(xtail)
free(zpow)
free(curR)
free(curC)
free(curV)
free(newR)
free(newC)
free(newV)
return total
}
function main() -> i32 {
let r: i64 = 10
let s: i64 = inv_mod(10)
let inv_r2: i64 = s * s % M
# prefix packages over the first k-1 letters of f
let A: ptr<i64> = calloc(7, 8)
let B: ptr<i64> = calloc(7, 8)
f_prefix_pkg(K - 1, r, inv_r2, A)
f_prefix_pkg(K - 1, s, r * r % M, B)
let Uk1: i64 = A[3]
let T0A: i64 = A[4]
let T1A: i64 = A[5]
let T2A: i64 = A[6]
let Vk1: i64 = B[3]
let T1B: i64 = B[5]
let T2B: i64 = B[6]
let r2k2: i64 = powmod(10, 2 * K - 2)
# edge windows: j=0 (0 + f-prefix) and j=k (reversed prefix + 1)
let W0sq: i64 = r2k2 * inv_r2 % M * (Vk1 * Vk1 % M) % M
let Wk: i64 = (10 * Uk1 + 1) % M
let Wksq: i64 = Wk * Wk % M
let term1: i64 = r2k2 * ((100 * T2A % M + 20 * T1A % M + T0A) % M) % M
let term3: i64 = inv_r2 * T2B % M
let term2b: i64 = 2 * T1B % M
# cross term via pair sums over upper-Wythoff numbers
let Es: i64 = pair_sum(s, K - 2) * 100 % M
let Er: i64 = pair_sum(10, K - 2) * inv_r2 % M
let inv99: i64 = inv_mod(99)
let gam: i64 = inv99 * ((r2k2 * Es % M - 10000 * Er % M + M) % M) % M
let term2a: i64 = 2 * s % M * gam % M
let psi: i64 = ((W0sq + Wksq) % M + (term1 + term2a) % M + (term2b + term3) % M) % M
printf("%lld\n", psi)
free(A)
free(B)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t powmod_i64_i64(int64_t base, int64_t exp);
int64_t inv_mod_i64(int64_t a0);
void pkg_merge_ptr_i64_ptr_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* out);
void pkg_set_ptr_i64_i64_i64_i64_i64_i64_i64_i64(int64_t* p, int64_t l, int64_t w, int64_t y, int64_t s, int64_t t0, int64_t t1, int64_t t2);
void pkg_copy_ptr_i64_ptr_i64(int64_t* dst, int64_t* src);
void f_prefix_pkg_i64_i64_i64_ptr_i64(int64_t N, int64_t om, int64_t y, int64_t* out);
int64_t pair_sum_i64_i64(int64_t z, int64_t X);
int32_t main(void);
static const int64_t M = 101001001;
static const int64_t K = 1000000000000000000;
int64_t powmod_i64_i64(int64_t base, int64_t exp) {
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (M));
int64_t e = exp;
while (e > 0) {
if ((e & 1) == 1) {
result = FLOW_CHECKED_MOD(((result * b)), (M));
}
b = FLOW_CHECKED_MOD(((b * b)), (M));
e = FLOW_CHECKED_SHR((e), (1));
}
return result;
}
int64_t inv_mod_i64(int64_t a0) {
int64_t g = M;
int64_t x = 0;
int64_t r = FLOW_CHECKED_MOD((a0), (M));
int64_t s = 1;
while (r != 0) {
int64_t q = FLOW_CHECKED_DIV((g), (r));
int64_t t = (g - (q * r));
g = r;
r = t;
int64_t u = (x - (q * s));
x = s;
s = u;
}
x = FLOW_CHECKED_MOD((x), (M));
if (x < 0) {
x = (x + M);
}
return x;
}
void pkg_merge_ptr_i64_ptr_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* out) {
int64_t La = a[0];
int64_t wA = a[1];
int64_t yA = a[2];
int64_t Sa = a[3];
int64_t T0a = a[4];
int64_t T1a = a[5];
int64_t T2a = a[6];
int64_t Lb = b[0];
int64_t wB = b[1];
int64_t yB = b[2];
int64_t Sb = b[3];
int64_t T0b = b[4];
int64_t T1b = b[5];
int64_t T2b = b[6];
out[0] = (La + Lb);
out[1] = FLOW_CHECKED_MOD(((wA * wB)), (M));
out[2] = FLOW_CHECKED_MOD(((yA * yB)), (M));
out[3] = FLOW_CHECKED_MOD(((Sa + (wA * Sb))), (M));
out[4] = FLOW_CHECKED_MOD(((T0a + (yA * T0b))), (M));
out[5] = FLOW_CHECKED_MOD(((T1a + (yA * FLOW_CHECKED_MOD((((Sa * T0b) + (wA * T1b))), (M))))), (M));
int64_t c1 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((Sa * Sa)), (M)) * T0b)), (M));
int64_t c2 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((2 * Sa)), (M)) * wA)), (M)) * T1b)), (M));
int64_t c3 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((wA * wA)), (M)) * T2b)), (M));
out[6] = FLOW_CHECKED_MOD(((T2a + (yA * FLOW_CHECKED_MOD((((c1 + c2) + c3)), (M))))), (M));
}
void pkg_set_ptr_i64_i64_i64_i64_i64_i64_i64_i64(int64_t* p, int64_t l, int64_t w, int64_t y, int64_t s, int64_t t0, int64_t t1, int64_t t2) {
p[0] = l;
p[1] = w;
p[2] = y;
p[3] = s;
p[4] = t0;
p[5] = t1;
p[6] = t2;
}
void pkg_copy_ptr_i64_ptr_i64(int64_t* dst, int64_t* src) {
int64_t i = 0;
while (i < 7) {
dst[i] = src[i];
i = (i + 1);
}
}
void f_prefix_pkg_i64_i64_i64_ptr_i64(int64_t N, int64_t om, int64_t y, int64_t* out) {
int64_t* blk = (int64_t*)(calloc((96 * 7), 8));
pkg_set_ptr_i64_i64_i64_i64_i64_i64_i64_i64((blk + (1 * 7)), 1, om, y, 0, 1, 0, 0);
int64_t* one = (int64_t*)(calloc(7, 8));
pkg_set_ptr_i64_i64_i64_i64_i64_i64_i64_i64(one, 1, om, y, 1, 1, 0, 0);
pkg_merge_ptr_i64_ptr_i64_ptr_i64((blk + (1 * 7)), one, (blk + (2 * 7)));
int64_t top = 2;
while (blk[((top * 7) + 0)] < N) {
top = (top + 1);
pkg_merge_ptr_i64_ptr_i64_ptr_i64((blk + ((top - 1) * 7)), (blk + ((top - 2) * 7)), (blk + (top * 7)));
}
int64_t* acc = (int64_t*)(calloc(7, 8));
int64_t* tmp = (int64_t*)(calloc(7, 8));
pkg_set_ptr_i64_i64_i64_i64_i64_i64_i64_i64(acc, 0, 1, 1, 0, 0, 0, 0);
int64_t n = top;
int64_t rem = N;
int64_t done = 0;
while (done == 0) {
if (rem == blk[((n * 7) + 0)]) {
pkg_merge_ptr_i64_ptr_i64_ptr_i64(acc, (blk + (n * 7)), tmp);
pkg_copy_ptr_i64_ptr_i64(acc, tmp);
done = 1;
} else {
if (n <= 2) {
pkg_merge_ptr_i64_ptr_i64_ptr_i64(acc, (blk + (1 * 7)), tmp);
pkg_copy_ptr_i64_ptr_i64(acc, tmp);
done = 1;
} else {
if (rem <= blk[(((n - 1) * 7) + 0)]) {
n = (n - 1);
} else {
pkg_merge_ptr_i64_ptr_i64_ptr_i64(acc, (blk + ((n - 1) * 7)), tmp);
pkg_copy_ptr_i64_ptr_i64(acc, tmp);
rem = (rem - blk[(((n - 1) * 7) + 0)]);
n = (n - 2);
}
}
}
}
pkg_copy_ptr_i64_ptr_i64(out, acc);
free(blk);
free(one);
free(acc);
free(tmp);
}
int64_t pair_sum_i64_i64(int64_t z, int64_t X) {
if (X < 4) {
return 0;
}
int64_t* F = (int64_t*)(calloc(96, 8));
F[2] = 1;
F[3] = 2;
int64_t nf = 3;
while (F[nf] < 4600000000000000000) {
nf = (nf + 1);
F[nf] = (F[(nf - 1)] + F[(nf - 2)]);
}
int64_t imax = 2;
while (F[(imax + 1)] <= X) {
imax = (imax + 1);
}
int64_t* xd = (int64_t*)(calloc(96, 8));
int64_t remx = X;
int64_t i = imax;
while (i >= 2) {
if (F[i] <= remx) {
xd[i] = 1;
remx = (remx - F[i]);
}
i = (i - 1);
}
int64_t* xtail = (int64_t*)(calloc(96, 8));
i = 3;
while (i <= imax) {
xtail[i] = (xtail[(i - 1)] + (xd[(i - 1)] * F[(i - 1)]));
i = (i + 1);
}
int64_t* zpow = (int64_t*)(calloc(96, 8));
i = 2;
while (i <= imax) {
zpow[i] = powmod_i64_i64(z, F[i]);
i = (i + 1);
}
int64_t CAP = 512;
int64_t* curR = (int64_t*)(calloc(CAP, 8));
int64_t* curC = (int64_t*)(calloc(CAP, 8));
int64_t* curV = (int64_t*)(calloc(CAP, 8));
int64_t* newR = (int64_t*)(calloc(CAP, 8));
int64_t* newC = (int64_t*)(calloc(CAP, 8));
int64_t* newV = (int64_t*)(calloc(CAP, 8));
int64_t ncur = 1;
curR[0] = 0;
curC[0] = 0;
curV[0] = 1;
i = imax;
while (i >= 2) {
int64_t xi = xd[i];
int64_t fi = F[i];
int64_t xt = xtail[i];
int64_t zp = zpow[i];
int64_t par = 1;
if ((i & 1) == 1) {
par = 2;
}
int64_t nnew = 0;
int64_t si = 0;
while (si < ncur) {
int64_t R = curR[si];
int64_t code = curC[si];
int64_t wgt = curV[si];
int64_t fr = FLOW_CHECKED_DIV((code), (36));
int64_t rest = FLOW_CHECKED_MOD((code), (36));
int64_t vp = FLOW_CHECKED_DIV((rest), (12));
int64_t up = FLOW_CHECKED_DIV((FLOW_CHECKED_MOD((rest), (12))), (4));
int64_t vl = FLOW_CHECKED_DIV((FLOW_CHECKED_MOD((rest), (4))), (2));
int64_t ul = FLOW_CHECKED_MOD((rest), (2));
int64_t ui = 0;
while (ui < 2) {
if ((ui == 1 && ul == 1)) {
ui = 2;
} else {
int64_t vi = 0;
while (vi < 2) {
if ((vi == 1 && vl == 1)) {
vi = 2;
} else {
int64_t nR = 0;
int64_t nfr = fr;
int64_t dead = 0;
if (fr == 0) {
nR = (R + (((xi - ui) - vi) * fi));
if ((nR + xt) < 0) {
dead = 1;
}
if (nR >= (2 * (fi - 1))) {
nfr = 1;
nR = 0;
}
}
if (dead == 0) {
int64_t nup = up;
if (ui == 1) {
nup = par;
}
int64_t nvp = vp;
if (vi == 1) {
nvp = par;
}
int64_t w2 = wgt;
if ((ui + vi) >= 1) {
w2 = FLOW_CHECKED_MOD(((w2 * zp)), (M));
}
if ((ui + vi) == 2) {
w2 = FLOW_CHECKED_MOD(((w2 * zp)), (M));
}
int64_t ncode = ((((ui + (2 * vi)) + (4 * nup)) + (12 * nvp)) + (36 * nfr));
int64_t hit = (0 - 1);
int64_t t = 0;
while (t < nnew) {
if ((newC[t] == ncode && newR[t] == nR)) {
hit = t;
t = nnew;
} else {
t = (t + 1);
}
}
if (hit >= 0) {
newV[hit] = FLOW_CHECKED_MOD(((newV[hit] + w2)), (M));
} else {
newR[nnew] = nR;
newC[nnew] = ncode;
newV[nnew] = w2;
nnew = (nnew + 1);
}
}
vi = (vi + 1);
}
}
ui = (ui + 1);
}
}
si = (si + 1);
}
int64_t t2 = 0;
while (t2 < nnew) {
curR[t2] = newR[t2];
curC[t2] = newC[t2];
curV[t2] = newV[t2];
t2 = (t2 + 1);
}
ncur = nnew;
i = (i - 1);
}
int64_t total = 0;
int64_t si2 = 0;
while (si2 < ncur) {
int64_t code = curC[si2];
int64_t fr = FLOW_CHECKED_DIV((code), (36));
int64_t rest = FLOW_CHECKED_MOD((code), (36));
int64_t vp = FLOW_CHECKED_DIV((rest), (12));
int64_t up = FLOW_CHECKED_DIV((FLOW_CHECKED_MOD((rest), (12))), (4));
if ((up == 2 && vp == 2)) {
if ((fr == 1 || curR[si2] >= 0)) {
total = FLOW_CHECKED_MOD(((total + curV[si2])), (M));
}
}
si2 = (si2 + 1);
}
free(F);
free(xd);
free(xtail);
free(zpow);
free(curR);
free(curC);
free(curV);
free(newR);
free(newC);
free(newV);
return total;
}
int32_t main(void) {
int64_t r = 10;
int64_t s = inv_mod_i64(10);
int64_t inv_r2 = FLOW_CHECKED_MOD(((s * s)), (M));
int64_t* A = (int64_t*)(calloc(7, 8));
int64_t* B = (int64_t*)(calloc(7, 8));
f_prefix_pkg_i64_i64_i64_ptr_i64((K - 1), r, inv_r2, A);
f_prefix_pkg_i64_i64_i64_ptr_i64((K - 1), s, FLOW_CHECKED_MOD(((r * r)), (M)), B);
int64_t Uk1 = A[3];
int64_t T0A = A[4];
int64_t T1A = A[5];
int64_t T2A = A[6];
int64_t Vk1 = B[3];
int64_t T1B = B[5];
int64_t T2B = B[6];
int64_t r2k2 = powmod_i64_i64(10, ((2 * K) - 2));
int64_t W0sq = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((r2k2 * inv_r2)), (M)) * FLOW_CHECKED_MOD(((Vk1 * Vk1)), (M)))), (M));
int64_t Wk = FLOW_CHECKED_MOD((((10 * Uk1) + 1)), (M));
int64_t Wksq = FLOW_CHECKED_MOD(((Wk * Wk)), (M));
int64_t term1 = FLOW_CHECKED_MOD(((r2k2 * FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((100 * T2A)), (M)) + FLOW_CHECKED_MOD(((20 * T1A)), (M))) + T0A)), (M)))), (M));
int64_t term3 = FLOW_CHECKED_MOD(((inv_r2 * T2B)), (M));
int64_t term2b = FLOW_CHECKED_MOD(((2 * T1B)), (M));
int64_t Es = FLOW_CHECKED_MOD(((pair_sum_i64_i64(s, (K - 2)) * 100)), (M));
int64_t Er = FLOW_CHECKED_MOD(((pair_sum_i64_i64(10, (K - 2)) * inv_r2)), (M));
int64_t inv99 = inv_mod_i64(99);
int64_t gam = FLOW_CHECKED_MOD(((inv99 * FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((r2k2 * Es)), (M)) - FLOW_CHECKED_MOD(((10000 * Er)), (M))) + M)), (M)))), (M));
int64_t term2a = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((2 * s)), (M)) * gam)), (M));
int64_t psi = FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((W0sq + Wksq)), (M)) + FLOW_CHECKED_MOD(((term1 + term2a)), (M))) + FLOW_CHECKED_MOD(((term2b + term3)), (M)))), (M));
printf("%lld\n", psi);
free(A);
free(B);
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: M
llvm.mlir.global internal constant @M(101001001 : i64) : i64
// Constant: K
llvm.mlir.global internal constant @K(1000000000000000000 : i64) : i64
func.func @powmod(%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 @M : !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 1 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.cmpi eq, %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 @M : !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 @M : !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 @inv_mod(%arg0: i64) -> i64 {
%39 = llvm.mlir.addressof @M : !llvm.ptr
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.mlir.constant(1 : i64) : i64
%42 = llvm.alloca %41 x i64 : (i64) -> !llvm.ptr
llvm.store %40, %42 : i64, !llvm.ptr
%43 = arith.constant 0 : i32
%44 = arith.extsi %43 : i32 to i64
%45 = llvm.mlir.constant(1 : i64) : i64
%46 = llvm.alloca %45 x i64 : (i64) -> !llvm.ptr
llvm.store %44, %46 : i64, !llvm.ptr
%47 = llvm.mlir.addressof @M : !llvm.ptr
%48 = llvm.load %47 : !llvm.ptr -> i64
%49 = arith.remsi %arg0, %48 : i64
%50 = llvm.mlir.constant(1 : i64) : i64
%51 = llvm.alloca %50 x i64 : (i64) -> !llvm.ptr
llvm.store %49, %51 : i64, !llvm.ptr
%52 = arith.constant 1 : i32
%53 = arith.extsi %52 : i32 to i64
%54 = llvm.mlir.constant(1 : i64) : i64
%55 = llvm.alloca %54 x i64 : (i64) -> !llvm.ptr
llvm.store %53, %55 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%56 = llvm.load %51 : !llvm.ptr -> i64
%57 = arith.constant 0 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.cmpi ne, %56, %59 : i64
cf.cond_br %58, ^bb7, ^bb8
^bb7:
%60 = llvm.load %42 : !llvm.ptr -> i64
%61 = llvm.load %51 : !llvm.ptr -> i64
%62 = arith.divsi %60, %61 : i64
%63 = llvm.load %42 : !llvm.ptr -> i64
%64 = llvm.load %51 : !llvm.ptr -> i64
%65 = arith.muli %62, %64 : i64
%66 = arith.subi %63, %65 : i64
%67 = llvm.load %51 : !llvm.ptr -> i64
llvm.store %67, %42 : i64, !llvm.ptr
llvm.store %66, %51 : i64, !llvm.ptr
%68 = llvm.load %46 : !llvm.ptr -> i64
%69 = llvm.load %55 : !llvm.ptr -> i64
%70 = arith.muli %62, %69 : i64
%71 = arith.subi %68, %70 : i64
%72 = llvm.load %55 : !llvm.ptr -> i64
llvm.store %72, %46 : i64, !llvm.ptr
llvm.store %71, %55 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%73 = llvm.load %46 : !llvm.ptr -> i64
%74 = llvm.mlir.addressof @M : !llvm.ptr
%75 = llvm.load %74 : !llvm.ptr -> i64
%76 = arith.remsi %73, %75 : i64
llvm.store %76, %46 : i64, !llvm.ptr
%77 = llvm.load %46 : !llvm.ptr -> i64
%78 = arith.constant 0 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.cmpi slt, %77, %80 : i64
cf.cond_br %79, ^bb9, ^bb10
^bb9:
%81 = llvm.load %46 : !llvm.ptr -> i64
%82 = llvm.mlir.addressof @M : !llvm.ptr
%83 = llvm.load %82 : !llvm.ptr -> i64
%84 = arith.addi %81, %83 : i64
llvm.store %84, %46 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%85 = llvm.load %46 : !llvm.ptr -> i64
func.return %85 : i64
}
func.func @pkg_merge(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%87 = arith.constant 0 : i32
%88 = arith.extsi %87 : i32 to i64
%89 = llvm.getelementptr %arg0[%88] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%86 = llvm.load %89 : !llvm.ptr -> i64
%91 = arith.constant 1 : i32
%92 = arith.extsi %91 : i32 to i64
%93 = llvm.getelementptr %arg0[%92] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%90 = llvm.load %93 : !llvm.ptr -> i64
%95 = arith.constant 2 : i32
%96 = arith.extsi %95 : i32 to i64
%97 = llvm.getelementptr %arg0[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%94 = llvm.load %97 : !llvm.ptr -> i64
%99 = arith.constant 3 : i32
%100 = arith.extsi %99 : i32 to i64
%101 = llvm.getelementptr %arg0[%100] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%98 = llvm.load %101 : !llvm.ptr -> i64
%103 = arith.constant 4 : i32
%104 = arith.extsi %103 : i32 to i64
%105 = llvm.getelementptr %arg0[%104] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%102 = llvm.load %105 : !llvm.ptr -> i64
%107 = arith.constant 5 : i32
%108 = arith.extsi %107 : i32 to i64
%109 = llvm.getelementptr %arg0[%108] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%106 = llvm.load %109 : !llvm.ptr -> i64
%111 = arith.constant 6 : i32
%112 = arith.extsi %111 : i32 to i64
%113 = llvm.getelementptr %arg0[%112] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%110 = llvm.load %113 : !llvm.ptr -> i64
%115 = arith.constant 0 : i32
%116 = arith.extsi %115 : i32 to i64
%117 = llvm.getelementptr %arg1[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%114 = llvm.load %117 : !llvm.ptr -> i64
%119 = arith.constant 1 : i32
%120 = arith.extsi %119 : i32 to i64
%121 = llvm.getelementptr %arg1[%120] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%118 = llvm.load %121 : !llvm.ptr -> i64
%123 = arith.constant 2 : i32
%124 = arith.extsi %123 : i32 to i64
%125 = llvm.getelementptr %arg1[%124] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%122 = llvm.load %125 : !llvm.ptr -> i64
%127 = arith.constant 3 : i32
%128 = arith.extsi %127 : i32 to i64
%129 = llvm.getelementptr %arg1[%128] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%126 = llvm.load %129 : !llvm.ptr -> i64
%131 = arith.constant 4 : i32
%132 = arith.extsi %131 : i32 to i64
%133 = llvm.getelementptr %arg1[%132] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%130 = llvm.load %133 : !llvm.ptr -> i64
%135 = arith.constant 5 : i32
%136 = arith.extsi %135 : i32 to i64
%137 = llvm.getelementptr %arg1[%136] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%134 = llvm.load %137 : !llvm.ptr -> i64
%139 = arith.constant 6 : i32
%140 = arith.extsi %139 : i32 to i64
%141 = llvm.getelementptr %arg1[%140] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%138 = llvm.load %141 : !llvm.ptr -> i64
%142 = arith.addi %86, %114 : i64
%143 = arith.constant 0 : i32
%144 = arith.extsi %143 : i32 to i64
%145 = llvm.getelementptr %arg2[%144] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %142, %145 : i64, !llvm.ptr
%146 = arith.muli %90, %118 : i64
%147 = llvm.mlir.addressof @M : !llvm.ptr
%148 = llvm.load %147 : !llvm.ptr -> i64
%149 = arith.remsi %146, %148 : i64
%150 = arith.constant 1 : i32
%151 = arith.extsi %150 : i32 to i64
%152 = llvm.getelementptr %arg2[%151] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %149, %152 : i64, !llvm.ptr
%153 = arith.muli %94, %122 : i64
%154 = llvm.mlir.addressof @M : !llvm.ptr
%155 = llvm.load %154 : !llvm.ptr -> i64
%156 = arith.remsi %153, %155 : i64
%157 = arith.constant 2 : i32
%158 = arith.extsi %157 : i32 to i64
%159 = llvm.getelementptr %arg2[%158] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %156, %159 : i64, !llvm.ptr
%160 = arith.muli %90, %126 : i64
%161 = arith.addi %98, %160 : i64
%162 = llvm.mlir.addressof @M : !llvm.ptr
%163 = llvm.load %162 : !llvm.ptr -> i64
%164 = arith.remsi %161, %163 : i64
%165 = arith.constant 3 : i32
%166 = arith.extsi %165 : i32 to i64
%167 = llvm.getelementptr %arg2[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %164, %167 : i64, !llvm.ptr
%168 = arith.muli %94, %130 : i64
%169 = arith.addi %102, %168 : i64
%170 = llvm.mlir.addressof @M : !llvm.ptr
%171 = llvm.load %170 : !llvm.ptr -> i64
%172 = arith.remsi %169, %171 : i64
%173 = arith.constant 4 : i32
%174 = arith.extsi %173 : i32 to i64
%175 = llvm.getelementptr %arg2[%174] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %172, %175 : i64, !llvm.ptr
%176 = arith.muli %98, %130 : i64
%177 = arith.muli %90, %134 : i64
%178 = arith.addi %176, %177 : i64
%179 = llvm.mlir.addressof @M : !llvm.ptr
%180 = llvm.load %179 : !llvm.ptr -> i64
%181 = arith.remsi %178, %180 : i64
%182 = arith.muli %94, %181 : i64
%183 = arith.addi %106, %182 : i64
%184 = llvm.mlir.addressof @M : !llvm.ptr
%185 = llvm.load %184 : !llvm.ptr -> i64
%186 = arith.remsi %183, %185 : i64
%187 = arith.constant 5 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.getelementptr %arg2[%188] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %186, %189 : i64, !llvm.ptr
%190 = arith.muli %98, %98 : i64
%191 = llvm.mlir.addressof @M : !llvm.ptr
%192 = llvm.load %191 : !llvm.ptr -> i64
%193 = arith.remsi %190, %192 : i64
%194 = arith.muli %193, %130 : i64
%195 = llvm.mlir.addressof @M : !llvm.ptr
%196 = llvm.load %195 : !llvm.ptr -> i64
%197 = arith.remsi %194, %196 : i64
%198 = arith.constant 2 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.muli %200, %98 : i64
%201 = llvm.mlir.addressof @M : !llvm.ptr
%202 = llvm.load %201 : !llvm.ptr -> i64
%203 = arith.remsi %199, %202 : i64
%204 = arith.muli %203, %90 : i64
%205 = llvm.mlir.addressof @M : !llvm.ptr
%206 = llvm.load %205 : !llvm.ptr -> i64
%207 = arith.remsi %204, %206 : i64
%208 = arith.muli %207, %134 : i64
%209 = llvm.mlir.addressof @M : !llvm.ptr
%210 = llvm.load %209 : !llvm.ptr -> i64
%211 = arith.remsi %208, %210 : i64
%212 = arith.muli %90, %90 : i64
%213 = llvm.mlir.addressof @M : !llvm.ptr
%214 = llvm.load %213 : !llvm.ptr -> i64
%215 = arith.remsi %212, %214 : i64
%216 = arith.muli %215, %138 : i64
%217 = llvm.mlir.addressof @M : !llvm.ptr
%218 = llvm.load %217 : !llvm.ptr -> i64
%219 = arith.remsi %216, %218 : i64
%220 = arith.addi %197, %211 : i64
%221 = arith.addi %220, %219 : i64
%222 = llvm.mlir.addressof @M : !llvm.ptr
%223 = llvm.load %222 : !llvm.ptr -> i64
%224 = arith.remsi %221, %223 : i64
%225 = arith.muli %94, %224 : i64
%226 = arith.addi %110, %225 : i64
%227 = llvm.mlir.addressof @M : !llvm.ptr
%228 = llvm.load %227 : !llvm.ptr -> i64
%229 = arith.remsi %226, %228 : i64
%230 = arith.constant 6 : i32
%231 = arith.extsi %230 : i32 to i64
%232 = llvm.getelementptr %arg2[%231] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %229, %232 : i64, !llvm.ptr
func.return
}
func.func @pkg_set(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: i64, %arg5: i64, %arg6: i64, %arg7: i64) -> () {
%233 = arith.constant 0 : i32
%234 = arith.extsi %233 : i32 to i64
%235 = llvm.getelementptr %arg0[%234] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %235 : i64, !llvm.ptr
%236 = arith.constant 1 : i32
%237 = arith.extsi %236 : i32 to i64
%238 = llvm.getelementptr %arg0[%237] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg2, %238 : i64, !llvm.ptr
%239 = arith.constant 2 : i32
%240 = arith.extsi %239 : i32 to i64
%241 = llvm.getelementptr %arg0[%240] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg3, %241 : i64, !llvm.ptr
%242 = arith.constant 3 : i32
%243 = arith.extsi %242 : i32 to i64
%244 = llvm.getelementptr %arg0[%243] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg4, %244 : i64, !llvm.ptr
%245 = arith.constant 4 : i32
%246 = arith.extsi %245 : i32 to i64
%247 = llvm.getelementptr %arg0[%246] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg5, %247 : i64, !llvm.ptr
%248 = arith.constant 5 : i32
%249 = arith.extsi %248 : i32 to i64
%250 = llvm.getelementptr %arg0[%249] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg6, %250 : i64, !llvm.ptr
%251 = arith.constant 6 : i32
%252 = arith.extsi %251 : i32 to i64
%253 = llvm.getelementptr %arg0[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg7, %253 : i64, !llvm.ptr
func.return
}
func.func @pkg_copy(%arg0: !llvm.ptr, %arg1: !llvm.ptr) -> () {
%254 = arith.constant 0 : i32
%255 = arith.extsi %254 : i32 to i64
%256 = llvm.mlir.constant(1 : i64) : i64
%257 = llvm.alloca %256 x i64 : (i64) -> !llvm.ptr
llvm.store %255, %257 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%258 = llvm.load %257 : !llvm.ptr -> i64
%259 = arith.constant 7 : i32
%261 = arith.extsi %259 : i32 to i64
%260 = arith.cmpi slt, %258, %261 : i64
cf.cond_br %260, ^bb13, ^bb14
^bb13:
%263 = llvm.load %257 : !llvm.ptr -> i64
%264 = llvm.getelementptr %arg1[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%262 = llvm.load %264 : !llvm.ptr -> i64
%265 = llvm.load %257 : !llvm.ptr -> i64
%266 = llvm.getelementptr %arg0[%265] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %262, %266 : i64, !llvm.ptr
%267 = llvm.load %257 : !llvm.ptr -> i64
%268 = arith.constant 1 : i32
%270 = arith.extsi %268 : i32 to i64
%269 = arith.addi %267, %270 : i64
llvm.store %269, %257 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
func.return
}
func.func @f_prefix_pkg(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr) -> () {
%272 = arith.constant 96 : i32
%273 = arith.constant 7 : i32
%274 = arith.muli %272, %273 : i32
%275 = arith.constant 8 : i32
%276 = arith.extsi %274 : i32 to i64
%277 = arith.extsi %275 : i32 to i64
%271 = func.call @calloc(%276, %277) : (i64, i64) -> !llvm.ptr
# String concatenation: !llvm.ptr + i32
%280 = arith.constant 1 : i32
%281 = arith.constant 0 : i32
%282 = arith.constant 1 : i32
%283 = arith.constant 0 : i32
%284 = arith.constant 0 : i32
%285 = arith.extsi %280 : i32 to i64
%286 = arith.extsi %281 : i32 to i64
%287 = arith.extsi %282 : i32 to i64
%288 = arith.extsi %283 : i32 to i64
%289 = arith.extsi %284 : i32 to i64
func.call @pkg_set(%279, %285, %arg1, %arg2, %286, %287, %288, %289) : (!llvm.ptr, i64, i64, i64, i64, i64, i64, i64) -> ()
%291 = arith.constant 7 : i32
%292 = arith.constant 8 : i32
%293 = arith.extsi %291 : i32 to i64
%294 = arith.extsi %292 : i32 to i64
%290 = func.call @calloc(%293, %294) : (i64, i64) -> !llvm.ptr
%296 = arith.constant 1 : i32
%297 = arith.constant 1 : i32
%298 = arith.constant 1 : i32
%299 = arith.constant 0 : i32
%300 = arith.constant 0 : i32
%301 = arith.extsi %296 : i32 to i64
%302 = arith.extsi %297 : i32 to i64
%303 = arith.extsi %298 : i32 to i64
%304 = arith.extsi %299 : i32 to i64
%305 = arith.extsi %300 : i32 to i64
func.call @pkg_set(%290, %301, %arg1, %arg2, %302, %303, %304, %305) : (!llvm.ptr, i64, i64, i64, i64, i64, i64, i64) -> ()
# String concatenation: !llvm.ptr + i32
# String concatenation: !llvm.ptr + i32
func.call @pkg_merge(%307, %290, %308) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%309 = arith.constant 2 : i32
%310 = arith.extsi %309 : i32 to i64
%311 = llvm.mlir.constant(1 : i64) : i64
%312 = llvm.alloca %311 x i64 : (i64) -> !llvm.ptr
llvm.store %310, %312 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%314 = llvm.load %312 : !llvm.ptr -> i64
%315 = arith.constant 7 : i32
%317 = arith.extsi %315 : i32 to i64
%316 = arith.muli %314, %317 : i64
%318 = arith.constant 0 : i32
%320 = arith.extsi %318 : i32 to i64
%319 = arith.addi %316, %320 : i64
%321 = llvm.getelementptr %271[%319] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%313 = llvm.load %321 : !llvm.ptr -> i64
%322 = arith.cmpi slt, %313, %arg0 : i64
cf.cond_br %322, ^bb16, ^bb17
^bb16:
%323 = llvm.load %312 : !llvm.ptr -> i64
%324 = arith.constant 1 : i32
%326 = arith.extsi %324 : i32 to i64
%325 = arith.addi %323, %326 : i64
llvm.store %325, %312 : i64, !llvm.ptr
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
# String concatenation: !llvm.ptr + i64
func.call @pkg_merge(%328, %329, %330) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb15
^bb17:
%332 = arith.constant 7 : i32
%333 = arith.constant 8 : 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 7 : 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 0 : i32
%343 = arith.constant 1 : i32
%344 = arith.constant 1 : i32
%345 = arith.constant 0 : i32
%346 = arith.constant 0 : i32
%347 = arith.constant 0 : i32
%348 = arith.constant 0 : i32
%349 = arith.extsi %342 : i32 to i64
%350 = arith.extsi %343 : i32 to i64
%351 = arith.extsi %344 : i32 to i64
%352 = arith.extsi %345 : i32 to i64
%353 = arith.extsi %346 : i32 to i64
%354 = arith.extsi %347 : i32 to i64
%355 = arith.extsi %348 : i32 to i64
func.call @pkg_set(%331, %349, %350, %351, %352, %353, %354, %355) : (!llvm.ptr, i64, i64, i64, i64, i64, i64, i64) -> ()
%356 = llvm.load %312 : !llvm.ptr -> i64
%357 = llvm.mlir.constant(1 : i64) : i64
%358 = llvm.alloca %357 x i64 : (i64) -> !llvm.ptr
llvm.store %356, %358 : i64, !llvm.ptr
%359 = llvm.mlir.constant(1 : i64) : i64
%360 = llvm.alloca %359 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %360 : i64, !llvm.ptr
%361 = arith.constant 0 : i32
%362 = arith.extsi %361 : i32 to i64
%363 = llvm.mlir.constant(1 : i64) : i64
%364 = llvm.alloca %363 x i64 : (i64) -> !llvm.ptr
llvm.store %362, %364 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%365 = llvm.load %364 : !llvm.ptr -> i64
%366 = arith.constant 0 : i32
%368 = arith.extsi %366 : i32 to i64
%367 = arith.cmpi eq, %365, %368 : i64
cf.cond_br %367, ^bb19, ^bb20
^bb19:
%369 = llvm.load %360 : !llvm.ptr -> i64
%371 = llvm.load %358 : !llvm.ptr -> i64
%372 = arith.constant 7 : i32
%374 = arith.extsi %372 : i32 to i64
%373 = arith.muli %371, %374 : i64
%375 = arith.constant 0 : i32
%377 = arith.extsi %375 : i32 to i64
%376 = arith.addi %373, %377 : i64
%378 = llvm.getelementptr %271[%376] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%370 = llvm.load %378 : !llvm.ptr -> i64
%379 = arith.cmpi eq, %369, %370 : i64
cf.cond_br %379, ^bb21, ^bb22
^bb21:
# String concatenation: !llvm.ptr + i64
func.call @pkg_merge(%331, %381, %336) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @pkg_copy(%331, %336) : (!llvm.ptr, !llvm.ptr) -> ()
%383 = arith.constant 1 : i32
%384 = arith.extsi %383 : i32 to i64
llvm.store %384, %364 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
%385 = llvm.load %358 : !llvm.ptr -> i64
%386 = arith.constant 2 : i32
%388 = arith.extsi %386 : i32 to i64
%387 = arith.cmpi sle, %385, %388 : i64
cf.cond_br %387, ^bb24, ^bb25
^bb24:
# String concatenation: !llvm.ptr + i32
func.call @pkg_merge(%331, %390, %336) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @pkg_copy(%331, %336) : (!llvm.ptr, !llvm.ptr) -> ()
%392 = arith.constant 1 : i32
%393 = arith.extsi %392 : i32 to i64
llvm.store %393, %364 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
%394 = llvm.load %360 : !llvm.ptr -> i64
%396 = llvm.load %358 : !llvm.ptr -> i64
%397 = arith.constant 1 : i32
%399 = arith.extsi %397 : i32 to i64
%398 = arith.subi %396, %399 : i64
%400 = arith.constant 7 : i32
%402 = arith.extsi %400 : i32 to i64
%401 = arith.muli %398, %402 : i64
%403 = arith.constant 0 : i32
%405 = arith.extsi %403 : i32 to i64
%404 = arith.addi %401, %405 : i64
%406 = llvm.getelementptr %271[%404] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%395 = llvm.load %406 : !llvm.ptr -> i64
%407 = arith.cmpi sle, %394, %395 : i64
cf.cond_br %407, ^bb27, ^bb28
^bb27:
%408 = llvm.load %358 : !llvm.ptr -> i64
%409 = arith.constant 1 : i32
%411 = arith.extsi %409 : i32 to i64
%410 = arith.subi %408, %411 : i64
llvm.store %410, %358 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
# String concatenation: !llvm.ptr + i64
func.call @pkg_merge(%331, %413, %336) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @pkg_copy(%331, %336) : (!llvm.ptr, !llvm.ptr) -> ()
%415 = llvm.load %360 : !llvm.ptr -> i64
%417 = llvm.load %358 : !llvm.ptr -> i64
%418 = arith.constant 1 : i32
%420 = arith.extsi %418 : i32 to i64
%419 = arith.subi %417, %420 : i64
%421 = arith.constant 7 : i32
%423 = arith.extsi %421 : i32 to i64
%422 = arith.muli %419, %423 : i64
%424 = arith.constant 0 : i32
%426 = arith.extsi %424 : i32 to i64
%425 = arith.addi %422, %426 : i64
%427 = llvm.getelementptr %271[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%416 = llvm.load %427 : !llvm.ptr -> i64
%428 = arith.subi %415, %416 : i64
llvm.store %428, %360 : i64, !llvm.ptr
%429 = llvm.load %358 : !llvm.ptr -> i64
%430 = arith.constant 2 : i32
%432 = arith.extsi %430 : i32 to i64
%431 = arith.subi %429, %432 : i64
llvm.store %431, %358 : i64, !llvm.ptr
cf.br ^bb29
^bb29:
cf.br ^bb26
^bb26:
cf.br ^bb23
^bb23:
cf.br ^bb18
^bb20:
func.call @pkg_copy(%arg3, %331) : (!llvm.ptr, !llvm.ptr) -> ()
func.call @free(%271) : (!llvm.ptr) -> ()
func.call @free(%290) : (!llvm.ptr) -> ()
func.call @free(%331) : (!llvm.ptr) -> ()
func.call @free(%336) : (!llvm.ptr) -> ()
func.return
}
func.func @pair_sum(%arg0: i64, %arg1: i64) -> i64 {
%438 = arith.constant 4 : i32
%440 = arith.extsi %438 : i32 to i64
%439 = arith.cmpi slt, %arg1, %440 : i64
cf.cond_br %439, ^bb30, ^bb31
^bb30:
%441 = arith.constant 0 : i32
%442 = arith.extsi %441 : i32 to i64
func.return %442 : i64
^bb31:
cf.br ^bb32
^bb32:
%444 = arith.constant 96 : i32
%445 = arith.constant 8 : i32
%446 = arith.extsi %444 : i32 to i64
%447 = arith.extsi %445 : i32 to i64
%443 = func.call @calloc(%446, %447) : (i64, i64) -> !llvm.ptr
%448 = arith.constant 1 : i32
%449 = arith.constant 2 : i32
%450 = arith.extsi %448 : i32 to i64
%451 = arith.extsi %449 : i32 to i64
%452 = llvm.getelementptr %443[%451] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %450, %452 : i64, !llvm.ptr
%453 = arith.constant 2 : i32
%454 = arith.constant 3 : i32
%455 = arith.extsi %453 : i32 to i64
%456 = arith.extsi %454 : i32 to i64
%457 = llvm.getelementptr %443[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %455, %457 : i64, !llvm.ptr
%458 = arith.constant 3 : i32
%459 = arith.extsi %458 : i32 to i64
%460 = llvm.mlir.constant(1 : i64) : i64
%461 = llvm.alloca %460 x i64 : (i64) -> !llvm.ptr
llvm.store %459, %461 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%463 = llvm.load %461 : !llvm.ptr -> i64
%464 = llvm.getelementptr %443[%463] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%462 = llvm.load %464 : !llvm.ptr -> i64
%465 = arith.constant 4599999995705032704 : i32
%467 = arith.extsi %465 : i32 to i64
%466 = arith.cmpi slt, %462, %467 : i64
cf.cond_br %466, ^bb34, ^bb35
^bb34:
%468 = llvm.load %461 : !llvm.ptr -> i64
%469 = arith.constant 1 : i32
%471 = arith.extsi %469 : i32 to i64
%470 = arith.addi %468, %471 : i64
llvm.store %470, %461 : i64, !llvm.ptr
%473 = llvm.load %461 : !llvm.ptr -> i64
%474 = arith.constant 1 : i32
%476 = arith.extsi %474 : i32 to i64
%475 = arith.subi %473, %476 : i64
%477 = llvm.getelementptr %443[%475] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%472 = llvm.load %477 : !llvm.ptr -> i64
%479 = llvm.load %461 : !llvm.ptr -> i64
%480 = arith.constant 2 : i32
%482 = arith.extsi %480 : i32 to i64
%481 = arith.subi %479, %482 : i64
%483 = llvm.getelementptr %443[%481] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%478 = llvm.load %483 : !llvm.ptr -> i64
%484 = arith.addi %472, %478 : i64
%485 = llvm.load %461 : !llvm.ptr -> i64
%486 = llvm.getelementptr %443[%485] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %484, %486 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%487 = arith.constant 2 : i32
%488 = arith.extsi %487 : i32 to i64
%489 = llvm.mlir.constant(1 : i64) : i64
%490 = llvm.alloca %489 x i64 : (i64) -> !llvm.ptr
llvm.store %488, %490 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%492 = llvm.load %490 : !llvm.ptr -> i64
%493 = arith.constant 1 : i32
%495 = arith.extsi %493 : i32 to i64
%494 = arith.addi %492, %495 : i64
%496 = llvm.getelementptr %443[%494] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%491 = llvm.load %496 : !llvm.ptr -> i64
%497 = arith.cmpi sle, %491, %arg1 : i64
cf.cond_br %497, ^bb37, ^bb38
^bb37:
%498 = llvm.load %490 : !llvm.ptr -> i64
%499 = arith.constant 1 : i32
%501 = arith.extsi %499 : i32 to i64
%500 = arith.addi %498, %501 : i64
llvm.store %500, %490 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%503 = arith.constant 96 : i32
%504 = arith.constant 8 : i32
%505 = arith.extsi %503 : i32 to i64
%506 = arith.extsi %504 : i32 to i64
%502 = func.call @calloc(%505, %506) : (i64, i64) -> !llvm.ptr
%507 = llvm.mlir.constant(1 : i64) : i64
%508 = llvm.alloca %507 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %508 : i64, !llvm.ptr
%509 = llvm.load %490 : !llvm.ptr -> i64
%510 = llvm.mlir.constant(1 : i64) : i64
%511 = llvm.alloca %510 x i64 : (i64) -> !llvm.ptr
llvm.store %509, %511 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%512 = llvm.load %511 : !llvm.ptr -> i64
%513 = arith.constant 2 : i32
%515 = arith.extsi %513 : i32 to i64
%514 = arith.cmpi sge, %512, %515 : i64
cf.cond_br %514, ^bb40, ^bb41
^bb40:
%517 = llvm.load %511 : !llvm.ptr -> i64
%518 = llvm.getelementptr %443[%517] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%516 = llvm.load %518 : !llvm.ptr -> i64
%519 = llvm.load %508 : !llvm.ptr -> i64
%520 = arith.cmpi sle, %516, %519 : i64
cf.cond_br %520, ^bb42, ^bb43
^bb42:
%521 = arith.constant 1 : i32
%522 = llvm.load %511 : !llvm.ptr -> i64
%523 = arith.extsi %521 : i32 to i64
%524 = llvm.getelementptr %502[%522] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %523, %524 : i64, !llvm.ptr
%525 = llvm.load %508 : !llvm.ptr -> i64
%527 = llvm.load %511 : !llvm.ptr -> i64
%528 = llvm.getelementptr %443[%527] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%526 = llvm.load %528 : !llvm.ptr -> i64
%529 = arith.subi %525, %526 : i64
llvm.store %529, %508 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%530 = llvm.load %511 : !llvm.ptr -> i64
%531 = arith.constant 1 : i32
%533 = arith.extsi %531 : i32 to i64
%532 = arith.subi %530, %533 : i64
llvm.store %532, %511 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
%535 = arith.constant 96 : i32
%536 = arith.constant 8 : i32
%537 = arith.extsi %535 : i32 to i64
%538 = arith.extsi %536 : i32 to i64
%534 = func.call @calloc(%537, %538) : (i64, i64) -> !llvm.ptr
%539 = arith.constant 3 : i32
%540 = arith.extsi %539 : i32 to i64
llvm.store %540, %511 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%541 = llvm.load %511 : !llvm.ptr -> i64
%542 = llvm.load %490 : !llvm.ptr -> i64
%543 = arith.cmpi sle, %541, %542 : i64
cf.cond_br %543, ^bb46, ^bb47
^bb46:
%545 = llvm.load %511 : !llvm.ptr -> i64
%546 = arith.constant 1 : i32
%548 = arith.extsi %546 : i32 to i64
%547 = arith.subi %545, %548 : i64
%549 = llvm.getelementptr %534[%547] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%544 = llvm.load %549 : !llvm.ptr -> i64
%551 = llvm.load %511 : !llvm.ptr -> i64
%552 = arith.constant 1 : i32
%554 = arith.extsi %552 : i32 to i64
%553 = arith.subi %551, %554 : i64
%555 = llvm.getelementptr %502[%553] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%550 = llvm.load %555 : !llvm.ptr -> i64
%557 = llvm.load %511 : !llvm.ptr -> i64
%558 = arith.constant 1 : i32
%560 = arith.extsi %558 : i32 to i64
%559 = arith.subi %557, %560 : i64
%561 = llvm.getelementptr %443[%559] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%556 = llvm.load %561 : !llvm.ptr -> i64
%562 = arith.muli %550, %556 : i64
%563 = arith.addi %544, %562 : i64
%564 = llvm.load %511 : !llvm.ptr -> i64
%565 = llvm.getelementptr %534[%564] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %563, %565 : i64, !llvm.ptr
%566 = llvm.load %511 : !llvm.ptr -> i64
%567 = arith.constant 1 : i32
%569 = arith.extsi %567 : i32 to i64
%568 = arith.addi %566, %569 : i64
llvm.store %568, %511 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%571 = arith.constant 96 : i32
%572 = arith.constant 8 : i32
%573 = arith.extsi %571 : i32 to i64
%574 = arith.extsi %572 : i32 to i64
%570 = func.call @calloc(%573, %574) : (i64, i64) -> !llvm.ptr
%575 = arith.constant 2 : i32
%576 = arith.extsi %575 : i32 to i64
llvm.store %576, %511 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%577 = llvm.load %511 : !llvm.ptr -> i64
%578 = llvm.load %490 : !llvm.ptr -> i64
%579 = arith.cmpi sle, %577, %578 : i64
cf.cond_br %579, ^bb49, ^bb50
^bb49:
%582 = llvm.load %511 : !llvm.ptr -> i64
%583 = llvm.getelementptr %443[%582] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%581 = llvm.load %583 : !llvm.ptr -> i64
%580 = func.call @powmod(%arg0, %581) : (i64, i64) -> i64
%584 = llvm.load %511 : !llvm.ptr -> i64
%585 = llvm.getelementptr %570[%584] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %580, %585 : i64, !llvm.ptr
%586 = llvm.load %511 : !llvm.ptr -> i64
%587 = arith.constant 1 : i32
%589 = arith.extsi %587 : i32 to i64
%588 = arith.addi %586, %589 : i64
llvm.store %588, %511 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%590 = arith.constant 512 : i32
%591 = arith.extsi %590 : i32 to i64
%593 = arith.constant 8 : i32
%594 = arith.extsi %593 : i32 to i64
%592 = func.call @calloc(%591, %594) : (i64, i64) -> !llvm.ptr
%596 = arith.constant 8 : i32
%597 = arith.extsi %596 : i32 to i64
%595 = func.call @calloc(%591, %597) : (i64, i64) -> !llvm.ptr
%599 = arith.constant 8 : i32
%600 = arith.extsi %599 : i32 to i64
%598 = func.call @calloc(%591, %600) : (i64, i64) -> !llvm.ptr
%602 = arith.constant 8 : i32
%603 = arith.extsi %602 : i32 to i64
%601 = func.call @calloc(%591, %603) : (i64, i64) -> !llvm.ptr
%605 = arith.constant 8 : i32
%606 = arith.extsi %605 : i32 to i64
%604 = func.call @calloc(%591, %606) : (i64, i64) -> !llvm.ptr
%608 = arith.constant 8 : i32
%609 = arith.extsi %608 : i32 to i64
%607 = func.call @calloc(%591, %609) : (i64, i64) -> !llvm.ptr
%610 = arith.constant 1 : i32
%611 = arith.extsi %610 : i32 to i64
%612 = llvm.mlir.constant(1 : i64) : i64
%613 = llvm.alloca %612 x i64 : (i64) -> !llvm.ptr
llvm.store %611, %613 : i64, !llvm.ptr
%614 = arith.constant 0 : i32
%615 = arith.constant 0 : i32
%616 = arith.extsi %614 : i32 to i64
%617 = arith.extsi %615 : i32 to i64
%618 = llvm.getelementptr %592[%617] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %616, %618 : i64, !llvm.ptr
%619 = arith.constant 0 : i32
%620 = arith.constant 0 : i32
%621 = arith.extsi %619 : i32 to i64
%622 = arith.extsi %620 : i32 to i64
%623 = llvm.getelementptr %595[%622] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %621, %623 : i64, !llvm.ptr
%624 = arith.constant 1 : i32
%625 = arith.constant 0 : i32
%626 = arith.extsi %624 : i32 to i64
%627 = arith.extsi %625 : i32 to i64
%628 = llvm.getelementptr %598[%627] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %626, %628 : i64, !llvm.ptr
%629 = llvm.load %490 : !llvm.ptr -> i64
llvm.store %629, %511 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%630 = llvm.load %511 : !llvm.ptr -> i64
%631 = arith.constant 2 : i32
%633 = arith.extsi %631 : i32 to i64
%632 = arith.cmpi sge, %630, %633 : i64
cf.cond_br %632, ^bb52, ^bb53
^bb52:
%635 = llvm.load %511 : !llvm.ptr -> i64
%636 = llvm.getelementptr %502[%635] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%634 = llvm.load %636 : !llvm.ptr -> i64
%638 = llvm.load %511 : !llvm.ptr -> i64
%639 = llvm.getelementptr %443[%638] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%637 = llvm.load %639 : !llvm.ptr -> i64
%641 = llvm.load %511 : !llvm.ptr -> i64
%642 = llvm.getelementptr %534[%641] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%640 = llvm.load %642 : !llvm.ptr -> i64
%644 = llvm.load %511 : !llvm.ptr -> i64
%645 = llvm.getelementptr %570[%644] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%643 = llvm.load %645 : !llvm.ptr -> i64
%646 = arith.constant 1 : i32
%647 = arith.extsi %646 : i32 to i64
%648 = llvm.mlir.constant(1 : i64) : i64
%649 = llvm.alloca %648 x i64 : (i64) -> !llvm.ptr
llvm.store %647, %649 : i64, !llvm.ptr
%650 = llvm.load %511 : !llvm.ptr -> i64
%651 = arith.constant 1 : i32
%653 = arith.extsi %651 : i32 to i64
%652 = arith.andi %650, %653 : i64
%654 = arith.constant 1 : i32
%656 = arith.extsi %654 : i32 to i64
%655 = arith.cmpi eq, %652, %656 : i64
cf.cond_br %655, ^bb54, ^bb55
^bb54:
%657 = arith.constant 2 : i32
%658 = arith.extsi %657 : i32 to i64
llvm.store %658, %649 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%659 = arith.constant 0 : i32
%660 = arith.extsi %659 : i32 to i64
%661 = llvm.mlir.constant(1 : i64) : i64
%662 = llvm.alloca %661 x i64 : (i64) -> !llvm.ptr
llvm.store %660, %662 : i64, !llvm.ptr
%663 = arith.constant 0 : i32
%664 = arith.extsi %663 : i32 to i64
%665 = llvm.mlir.constant(1 : i64) : i64
%666 = llvm.alloca %665 x i64 : (i64) -> !llvm.ptr
llvm.store %664, %666 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%667 = llvm.load %666 : !llvm.ptr -> i64
%668 = llvm.load %613 : !llvm.ptr -> i64
%669 = arith.cmpi slt, %667, %668 : i64
cf.cond_br %669, ^bb58, ^bb59
^bb58:
%671 = llvm.load %666 : !llvm.ptr -> i64
%672 = llvm.getelementptr %592[%671] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%670 = llvm.load %672 : !llvm.ptr -> i64
%674 = llvm.load %666 : !llvm.ptr -> i64
%675 = llvm.getelementptr %595[%674] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%673 = llvm.load %675 : !llvm.ptr -> i64
%677 = llvm.load %666 : !llvm.ptr -> i64
%678 = llvm.getelementptr %598[%677] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%676 = llvm.load %678 : !llvm.ptr -> i64
%679 = arith.constant 36 : i32
%681 = arith.extsi %679 : i32 to i64
%680 = arith.divsi %673, %681 : i64
%682 = arith.constant 36 : i32
%684 = arith.extsi %682 : i32 to i64
%683 = arith.remsi %673, %684 : i64
%685 = arith.constant 12 : i32
%687 = arith.extsi %685 : i32 to i64
%686 = arith.divsi %683, %687 : i64
%688 = arith.constant 12 : i32
%690 = arith.extsi %688 : i32 to i64
%689 = arith.remsi %683, %690 : i64
%691 = arith.constant 4 : i32
%693 = arith.extsi %691 : i32 to i64
%692 = arith.divsi %689, %693 : i64
%694 = arith.constant 4 : i32
%696 = arith.extsi %694 : i32 to i64
%695 = arith.remsi %683, %696 : i64
%697 = arith.constant 2 : i32
%699 = arith.extsi %697 : i32 to i64
%698 = arith.divsi %695, %699 : i64
%700 = arith.constant 2 : i32
%702 = arith.extsi %700 : i32 to i64
%701 = arith.remsi %683, %702 : i64
%703 = arith.constant 0 : i32
%704 = arith.extsi %703 : i32 to i64
%705 = llvm.mlir.constant(1 : i64) : i64
%706 = llvm.alloca %705 x i64 : (i64) -> !llvm.ptr
llvm.store %704, %706 : i64, !llvm.ptr
cf.br ^bb60
^bb60:
%707 = llvm.load %706 : !llvm.ptr -> i64
%708 = arith.constant 2 : i32
%710 = arith.extsi %708 : i32 to i64
%709 = arith.cmpi slt, %707, %710 : i64
cf.cond_br %709, ^bb61, ^bb62
^bb61:
%711 = llvm.load %706 : !llvm.ptr -> i64
%712 = arith.constant 1 : i32
%714 = arith.extsi %712 : i32 to i64
%713 = arith.cmpi eq, %711, %714 : i64
%715 = scf.if %713 -> (i1) {
%716 = arith.constant 1 : i32
%718 = arith.extsi %716 : i32 to i64
%717 = arith.cmpi eq, %701, %718 : i64
scf.yield %717 : i1
} else {
%719 = arith.constant false
scf.yield %719 : i1
}
cf.cond_br %715, ^bb63, ^bb64
^bb63:
%720 = arith.constant 2 : i32
%721 = arith.extsi %720 : i32 to i64
llvm.store %721, %706 : i64, !llvm.ptr
cf.br ^bb65
^bb64:
%722 = arith.constant 0 : i32
%723 = arith.extsi %722 : i32 to i64
%724 = llvm.mlir.constant(1 : i64) : i64
%725 = llvm.alloca %724 x i64 : (i64) -> !llvm.ptr
llvm.store %723, %725 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%726 = llvm.load %725 : !llvm.ptr -> i64
%727 = arith.constant 2 : i32
%729 = arith.extsi %727 : i32 to i64
%728 = arith.cmpi slt, %726, %729 : i64
cf.cond_br %728, ^bb67, ^bb68
^bb67:
%730 = llvm.load %725 : !llvm.ptr -> i64
%731 = arith.constant 1 : i32
%733 = arith.extsi %731 : i32 to i64
%732 = arith.cmpi eq, %730, %733 : i64
%734 = scf.if %732 -> (i1) {
%735 = arith.constant 1 : i32
%737 = arith.extsi %735 : i32 to i64
%736 = arith.cmpi eq, %698, %737 : i64
scf.yield %736 : i1
} else {
%738 = arith.constant false
scf.yield %738 : i1
}
cf.cond_br %734, ^bb69, ^bb70
^bb69:
%739 = arith.constant 2 : i32
%740 = arith.extsi %739 : i32 to i64
llvm.store %740, %725 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
%741 = arith.constant 0 : i32
%742 = arith.extsi %741 : i32 to i64
%743 = llvm.mlir.constant(1 : i64) : i64
%744 = llvm.alloca %743 x i64 : (i64) -> !llvm.ptr
llvm.store %742, %744 : i64, !llvm.ptr
%745 = llvm.mlir.constant(1 : i64) : i64
%746 = llvm.alloca %745 x i64 : (i64) -> !llvm.ptr
llvm.store %680, %746 : i64, !llvm.ptr
%747 = arith.constant 0 : i32
%748 = arith.extsi %747 : i32 to i64
%749 = llvm.mlir.constant(1 : i64) : i64
%750 = llvm.alloca %749 x i64 : (i64) -> !llvm.ptr
llvm.store %748, %750 : i64, !llvm.ptr
%751 = arith.constant 0 : i32
%753 = arith.extsi %751 : i32 to i64
%752 = arith.cmpi eq, %680, %753 : i64
cf.cond_br %752, ^bb72, ^bb73
^bb72:
%754 = llvm.load %706 : !llvm.ptr -> i64
%755 = arith.subi %634, %754 : i64
%756 = llvm.load %725 : !llvm.ptr -> i64
%757 = arith.subi %755, %756 : i64
%758 = arith.muli %757, %637 : i64
%759 = arith.addi %670, %758 : i64
llvm.store %759, %744 : i64, !llvm.ptr
%760 = llvm.load %744 : !llvm.ptr -> i64
%761 = arith.addi %760, %640 : i64
%762 = arith.constant 0 : i32
%764 = arith.extsi %762 : i32 to i64
%763 = arith.cmpi slt, %761, %764 : i64
cf.cond_br %763, ^bb75, ^bb76
^bb75:
%765 = arith.constant 1 : i32
%766 = arith.extsi %765 : i32 to i64
llvm.store %766, %750 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
%767 = llvm.load %744 : !llvm.ptr -> i64
%768 = arith.constant 2 : i32
%769 = arith.constant 1 : i32
%771 = arith.extsi %769 : i32 to i64
%770 = arith.subi %637, %771 : i64
%773 = arith.extsi %768 : i32 to i64
%772 = arith.muli %773, %770 : i64
%774 = arith.cmpi sge, %767, %772 : i64
cf.cond_br %774, ^bb78, ^bb79
^bb78:
%775 = arith.constant 1 : i32
%776 = arith.extsi %775 : i32 to i64
llvm.store %776, %746 : i64, !llvm.ptr
%777 = arith.constant 0 : i32
%778 = arith.extsi %777 : i32 to i64
llvm.store %778, %744 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
%779 = llvm.load %750 : !llvm.ptr -> i64
%780 = arith.constant 0 : i32
%782 = arith.extsi %780 : i32 to i64
%781 = arith.cmpi eq, %779, %782 : i64
cf.cond_br %781, ^bb81, ^bb82
^bb81:
%783 = llvm.mlir.constant(1 : i64) : i64
%784 = llvm.alloca %783 x i64 : (i64) -> !llvm.ptr
llvm.store %692, %784 : i64, !llvm.ptr
%785 = llvm.load %706 : !llvm.ptr -> i64
%786 = arith.constant 1 : i32
%788 = arith.extsi %786 : i32 to i64
%787 = arith.cmpi eq, %785, %788 : i64
cf.cond_br %787, ^bb84, ^bb85
^bb84:
%789 = llvm.load %649 : !llvm.ptr -> i64
llvm.store %789, %784 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%790 = llvm.mlir.constant(1 : i64) : i64
%791 = llvm.alloca %790 x i64 : (i64) -> !llvm.ptr
llvm.store %686, %791 : i64, !llvm.ptr
%792 = llvm.load %725 : !llvm.ptr -> i64
%793 = arith.constant 1 : i32
%795 = arith.extsi %793 : i32 to i64
%794 = arith.cmpi eq, %792, %795 : i64
cf.cond_br %794, ^bb87, ^bb88
^bb87:
%796 = llvm.load %649 : !llvm.ptr -> i64
llvm.store %796, %791 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%797 = llvm.mlir.constant(1 : i64) : i64
%798 = llvm.alloca %797 x i64 : (i64) -> !llvm.ptr
llvm.store %676, %798 : i64, !llvm.ptr
%799 = llvm.load %706 : !llvm.ptr -> i64
%800 = llvm.load %725 : !llvm.ptr -> i64
%801 = arith.addi %799, %800 : i64
%802 = arith.constant 1 : i32
%804 = arith.extsi %802 : i32 to i64
%803 = arith.cmpi sge, %801, %804 : i64
cf.cond_br %803, ^bb90, ^bb91
^bb90:
%805 = llvm.load %798 : !llvm.ptr -> i64
%806 = arith.muli %805, %643 : i64
%807 = llvm.mlir.addressof @M : !llvm.ptr
%808 = llvm.load %807 : !llvm.ptr -> i64
%809 = arith.remsi %806, %808 : i64
llvm.store %809, %798 : i64, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%810 = llvm.load %706 : !llvm.ptr -> i64
%811 = llvm.load %725 : !llvm.ptr -> i64
%812 = arith.addi %810, %811 : i64
%813 = arith.constant 2 : i32
%815 = arith.extsi %813 : i32 to i64
%814 = arith.cmpi eq, %812, %815 : i64
cf.cond_br %814, ^bb93, ^bb94
^bb93:
%816 = llvm.load %798 : !llvm.ptr -> i64
%817 = arith.muli %816, %643 : i64
%818 = llvm.mlir.addressof @M : !llvm.ptr
%819 = llvm.load %818 : !llvm.ptr -> i64
%820 = arith.remsi %817, %819 : i64
llvm.store %820, %798 : i64, !llvm.ptr
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
%821 = llvm.load %706 : !llvm.ptr -> i64
%822 = arith.constant 2 : i32
%823 = llvm.load %725 : !llvm.ptr -> i64
%825 = arith.extsi %822 : i32 to i64
%824 = arith.muli %825, %823 : i64
%826 = arith.addi %821, %824 : i64
%827 = arith.constant 4 : i32
%828 = llvm.load %784 : !llvm.ptr -> i64
%830 = arith.extsi %827 : i32 to i64
%829 = arith.muli %830, %828 : i64
%831 = arith.addi %826, %829 : i64
%832 = arith.constant 12 : i32
%833 = llvm.load %791 : !llvm.ptr -> i64
%835 = arith.extsi %832 : i32 to i64
%834 = arith.muli %835, %833 : i64
%836 = arith.addi %831, %834 : i64
%837 = arith.constant 36 : i32
%838 = llvm.load %746 : !llvm.ptr -> i64
%840 = arith.extsi %837 : i32 to i64
%839 = arith.muli %840, %838 : i64
%841 = arith.addi %836, %839 : i64
%842 = arith.constant 0 : i32
%843 = arith.constant 1 : i32
%844 = arith.subi %842, %843 : i32
%845 = arith.extsi %844 : i32 to i64
%846 = llvm.mlir.constant(1 : i64) : i64
%847 = llvm.alloca %846 x i64 : (i64) -> !llvm.ptr
llvm.store %845, %847 : i64, !llvm.ptr
%848 = arith.constant 0 : i32
%849 = arith.extsi %848 : i32 to i64
%850 = llvm.mlir.constant(1 : i64) : i64
%851 = llvm.alloca %850 x i64 : (i64) -> !llvm.ptr
llvm.store %849, %851 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%852 = llvm.load %851 : !llvm.ptr -> i64
%853 = llvm.load %662 : !llvm.ptr -> i64
%854 = arith.cmpi slt, %852, %853 : i64
cf.cond_br %854, ^bb97, ^bb98
^bb97:
%856 = llvm.load %851 : !llvm.ptr -> i64
%857 = llvm.getelementptr %604[%856] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%855 = llvm.load %857 : !llvm.ptr -> i64
%858 = arith.cmpi eq, %855, %841 : i64
%859 = scf.if %858 -> (i1) {
%861 = llvm.load %851 : !llvm.ptr -> i64
%862 = llvm.getelementptr %601[%861] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%860 = llvm.load %862 : !llvm.ptr -> i64
%863 = llvm.load %744 : !llvm.ptr -> i64
%864 = arith.cmpi eq, %860, %863 : i64
scf.yield %864 : i1
} else {
%865 = arith.constant false
scf.yield %865 : i1
}
cf.cond_br %859, ^bb99, ^bb100
^bb99:
%866 = llvm.load %851 : !llvm.ptr -> i64
llvm.store %866, %847 : i64, !llvm.ptr
%867 = llvm.load %662 : !llvm.ptr -> i64
llvm.store %867, %851 : i64, !llvm.ptr
cf.br ^bb101
^bb100:
%868 = llvm.load %851 : !llvm.ptr -> i64
%869 = arith.constant 1 : i32
%871 = arith.extsi %869 : i32 to i64
%870 = arith.addi %868, %871 : i64
llvm.store %870, %851 : i64, !llvm.ptr
cf.br ^bb101
^bb101:
cf.br ^bb96
^bb98:
%872 = llvm.load %847 : !llvm.ptr -> i64
%873 = arith.constant 0 : i32
%875 = arith.extsi %873 : i32 to i64
%874 = arith.cmpi sge, %872, %875 : i64
cf.cond_br %874, ^bb102, ^bb103
^bb102:
%877 = llvm.load %847 : !llvm.ptr -> i64
%878 = llvm.getelementptr %607[%877] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%876 = llvm.load %878 : !llvm.ptr -> i64
%879 = llvm.load %798 : !llvm.ptr -> i64
%880 = arith.addi %876, %879 : i64
%881 = llvm.mlir.addressof @M : !llvm.ptr
%882 = llvm.load %881 : !llvm.ptr -> i64
%883 = arith.remsi %880, %882 : i64
%884 = llvm.load %847 : !llvm.ptr -> i64
%885 = llvm.getelementptr %607[%884] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %883, %885 : i64, !llvm.ptr
cf.br ^bb104
^bb103:
%886 = llvm.load %744 : !llvm.ptr -> i64
%887 = llvm.load %662 : !llvm.ptr -> i64
%888 = llvm.getelementptr %601[%887] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %886, %888 : i64, !llvm.ptr
%889 = llvm.load %662 : !llvm.ptr -> i64
%890 = llvm.getelementptr %604[%889] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %841, %890 : i64, !llvm.ptr
%891 = llvm.load %798 : !llvm.ptr -> i64
%892 = llvm.load %662 : !llvm.ptr -> i64
%893 = llvm.getelementptr %607[%892] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %891, %893 : i64, !llvm.ptr
%894 = llvm.load %662 : !llvm.ptr -> i64
%895 = arith.constant 1 : i32
%897 = arith.extsi %895 : i32 to i64
%896 = arith.addi %894, %897 : i64
llvm.store %896, %662 : i64, !llvm.ptr
cf.br ^bb104
^bb104:
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%898 = llvm.load %725 : !llvm.ptr -> i64
%899 = arith.constant 1 : i32
%901 = arith.extsi %899 : i32 to i64
%900 = arith.addi %898, %901 : i64
llvm.store %900, %725 : i64, !llvm.ptr
cf.br ^bb71
^bb71:
cf.br ^bb66
^bb68:
%902 = llvm.load %706 : !llvm.ptr -> i64
%903 = arith.constant 1 : i32
%905 = arith.extsi %903 : i32 to i64
%904 = arith.addi %902, %905 : i64
llvm.store %904, %706 : i64, !llvm.ptr
cf.br ^bb65
^bb65:
cf.br ^bb60
^bb62:
%906 = llvm.load %666 : !llvm.ptr -> i64
%907 = arith.constant 1 : i32
%909 = arith.extsi %907 : i32 to i64
%908 = arith.addi %906, %909 : i64
llvm.store %908, %666 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%910 = arith.constant 0 : i32
%911 = arith.extsi %910 : i32 to i64
%912 = llvm.mlir.constant(1 : i64) : i64
%913 = llvm.alloca %912 x i64 : (i64) -> !llvm.ptr
llvm.store %911, %913 : i64, !llvm.ptr
cf.br ^bb105
^bb105:
%914 = llvm.load %913 : !llvm.ptr -> i64
%915 = llvm.load %662 : !llvm.ptr -> i64
%916 = arith.cmpi slt, %914, %915 : i64
cf.cond_br %916, ^bb106, ^bb107
^bb106:
%918 = llvm.load %913 : !llvm.ptr -> i64
%919 = llvm.getelementptr %601[%918] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%917 = llvm.load %919 : !llvm.ptr -> i64
%920 = llvm.load %913 : !llvm.ptr -> i64
%921 = llvm.getelementptr %592[%920] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %917, %921 : i64, !llvm.ptr
%923 = llvm.load %913 : !llvm.ptr -> i64
%924 = llvm.getelementptr %604[%923] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%922 = llvm.load %924 : !llvm.ptr -> i64
%925 = llvm.load %913 : !llvm.ptr -> i64
%926 = llvm.getelementptr %595[%925] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %922, %926 : i64, !llvm.ptr
%928 = llvm.load %913 : !llvm.ptr -> i64
%929 = llvm.getelementptr %607[%928] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%927 = llvm.load %929 : !llvm.ptr -> i64
%930 = llvm.load %913 : !llvm.ptr -> i64
%931 = llvm.getelementptr %598[%930] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %927, %931 : i64, !llvm.ptr
%932 = llvm.load %913 : !llvm.ptr -> i64
%933 = arith.constant 1 : i32
%935 = arith.extsi %933 : i32 to i64
%934 = arith.addi %932, %935 : i64
llvm.store %934, %913 : i64, !llvm.ptr
cf.br ^bb105
^bb107:
%936 = llvm.load %662 : !llvm.ptr -> i64
llvm.store %936, %613 : i64, !llvm.ptr
%937 = llvm.load %511 : !llvm.ptr -> i64
%938 = arith.constant 1 : i32
%940 = arith.extsi %938 : i32 to i64
%939 = arith.subi %937, %940 : i64
llvm.store %939, %511 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%941 = arith.constant 0 : i32
%942 = arith.extsi %941 : i32 to i64
%943 = llvm.mlir.constant(1 : i64) : i64
%944 = llvm.alloca %943 x i64 : (i64) -> !llvm.ptr
llvm.store %942, %944 : i64, !llvm.ptr
%945 = arith.constant 0 : i32
%946 = arith.extsi %945 : i32 to i64
%947 = llvm.mlir.constant(1 : i64) : i64
%948 = llvm.alloca %947 x i64 : (i64) -> !llvm.ptr
llvm.store %946, %948 : i64, !llvm.ptr
cf.br ^bb108
^bb108:
%949 = llvm.load %948 : !llvm.ptr -> i64
%950 = llvm.load %613 : !llvm.ptr -> i64
%951 = arith.cmpi slt, %949, %950 : i64
cf.cond_br %951, ^bb109, ^bb110
^bb109:
%953 = llvm.load %948 : !llvm.ptr -> i64
%954 = llvm.getelementptr %595[%953] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%952 = llvm.load %954 : !llvm.ptr -> i64
%955 = arith.constant 36 : i32
%957 = arith.extsi %955 : i32 to i64
%956 = arith.divsi %952, %957 : i64
%958 = arith.constant 36 : i32
%960 = arith.extsi %958 : i32 to i64
%959 = arith.remsi %952, %960 : i64
%961 = arith.constant 12 : i32
%963 = arith.extsi %961 : i32 to i64
%962 = arith.divsi %959, %963 : i64
%964 = arith.constant 12 : i32
%966 = arith.extsi %964 : i32 to i64
%965 = arith.remsi %959, %966 : i64
%967 = arith.constant 4 : i32
%969 = arith.extsi %967 : i32 to i64
%968 = arith.divsi %965, %969 : i64
%970 = arith.constant 2 : i32
%972 = arith.extsi %970 : i32 to i64
%971 = arith.cmpi eq, %968, %972 : i64
%973 = scf.if %971 -> (i1) {
%974 = arith.constant 2 : i32
%976 = arith.extsi %974 : i32 to i64
%975 = arith.cmpi eq, %962, %976 : i64
scf.yield %975 : i1
} else {
%977 = arith.constant false
scf.yield %977 : i1
}
cf.cond_br %973, ^bb111, ^bb112
^bb111:
%978 = arith.constant 1 : i32
%980 = arith.extsi %978 : i32 to i64
%979 = arith.cmpi eq, %956, %980 : i64
%981 = scf.if %979 -> (i1) {
%982 = arith.constant true
scf.yield %982 : i1
} else {
%984 = llvm.load %948 : !llvm.ptr -> i64
%985 = llvm.getelementptr %592[%984] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%983 = llvm.load %985 : !llvm.ptr -> i64
%986 = arith.constant 0 : i32
%988 = arith.extsi %986 : i32 to i64
%987 = arith.cmpi sge, %983, %988 : i64
scf.yield %987 : i1
}
cf.cond_br %981, ^bb114, ^bb115
^bb114:
%989 = llvm.load %944 : !llvm.ptr -> i64
%991 = llvm.load %948 : !llvm.ptr -> i64
%992 = llvm.getelementptr %598[%991] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%990 = llvm.load %992 : !llvm.ptr -> i64
%993 = arith.addi %989, %990 : i64
%994 = llvm.mlir.addressof @M : !llvm.ptr
%995 = llvm.load %994 : !llvm.ptr -> i64
%996 = arith.remsi %993, %995 : i64
llvm.store %996, %944 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
cf.br ^bb113
^bb112:
cf.br ^bb113
^bb113:
%997 = llvm.load %948 : !llvm.ptr -> i64
%998 = arith.constant 1 : i32
%1000 = arith.extsi %998 : i32 to i64
%999 = arith.addi %997, %1000 : i64
llvm.store %999, %948 : i64, !llvm.ptr
cf.br ^bb108
^bb110:
func.call @free(%443) : (!llvm.ptr) -> ()
func.call @free(%502) : (!llvm.ptr) -> ()
func.call @free(%534) : (!llvm.ptr) -> ()
func.call @free(%570) : (!llvm.ptr) -> ()
func.call @free(%592) : (!llvm.ptr) -> ()
func.call @free(%595) : (!llvm.ptr) -> ()
func.call @free(%598) : (!llvm.ptr) -> ()
func.call @free(%601) : (!llvm.ptr) -> ()
func.call @free(%604) : (!llvm.ptr) -> ()
func.call @free(%607) : (!llvm.ptr) -> ()
%1011 = llvm.load %944 : !llvm.ptr -> i64
func.return %1011 : i64
}
func.func @main() -> i32 {
%1012 = arith.constant 10 : i32
%1013 = arith.extsi %1012 : i32 to i64
%1015 = arith.constant 10 : i32
%1016 = arith.extsi %1015 : i32 to i64
%1014 = func.call @inv_mod(%1016) : (i64) -> i64
%1017 = arith.muli %1014, %1014 : i64
%1018 = llvm.mlir.addressof @M : !llvm.ptr
%1019 = llvm.load %1018 : !llvm.ptr -> i64
%1020 = arith.remsi %1017, %1019 : i64
%1022 = arith.constant 7 : i32
%1023 = arith.constant 8 : i32
%1024 = arith.extsi %1022 : i32 to i64
%1025 = arith.extsi %1023 : i32 to i64
%1021 = func.call @calloc(%1024, %1025) : (i64, i64) -> !llvm.ptr
%1027 = arith.constant 7 : i32
%1028 = arith.constant 8 : i32
%1029 = arith.extsi %1027 : i32 to i64
%1030 = arith.extsi %1028 : i32 to i64
%1026 = func.call @calloc(%1029, %1030) : (i64, i64) -> !llvm.ptr
%1032 = llvm.mlir.addressof @K : !llvm.ptr
%1033 = llvm.load %1032 : !llvm.ptr -> i64
%1034 = arith.constant 1 : i32
%1036 = arith.extsi %1034 : i32 to i64
%1035 = arith.subi %1033, %1036 : i64
func.call @f_prefix_pkg(%1035, %1013, %1020, %1021) : (i64, i64, i64, !llvm.ptr) -> ()
%1038 = llvm.mlir.addressof @K : !llvm.ptr
%1039 = llvm.load %1038 : !llvm.ptr -> i64
%1040 = arith.constant 1 : i32
%1042 = arith.extsi %1040 : i32 to i64
%1041 = arith.subi %1039, %1042 : i64
%1043 = arith.muli %1013, %1013 : i64
%1044 = llvm.mlir.addressof @M : !llvm.ptr
%1045 = llvm.load %1044 : !llvm.ptr -> i64
%1046 = arith.remsi %1043, %1045 : i64
func.call @f_prefix_pkg(%1041, %1014, %1046, %1026) : (i64, i64, i64, !llvm.ptr) -> ()
%1048 = arith.constant 3 : i32
%1049 = arith.extsi %1048 : i32 to i64
%1050 = llvm.getelementptr %1021[%1049] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1047 = llvm.load %1050 : !llvm.ptr -> i64
%1052 = arith.constant 4 : i32
%1053 = arith.extsi %1052 : i32 to i64
%1054 = llvm.getelementptr %1021[%1053] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1051 = llvm.load %1054 : !llvm.ptr -> i64
%1056 = arith.constant 5 : i32
%1057 = arith.extsi %1056 : i32 to i64
%1058 = llvm.getelementptr %1021[%1057] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1055 = llvm.load %1058 : !llvm.ptr -> i64
%1060 = arith.constant 6 : i32
%1061 = arith.extsi %1060 : i32 to i64
%1062 = llvm.getelementptr %1021[%1061] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1059 = llvm.load %1062 : !llvm.ptr -> i64
%1064 = arith.constant 3 : i32
%1065 = arith.extsi %1064 : i32 to i64
%1066 = llvm.getelementptr %1026[%1065] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1063 = llvm.load %1066 : !llvm.ptr -> i64
%1068 = arith.constant 5 : i32
%1069 = arith.extsi %1068 : i32 to i64
%1070 = llvm.getelementptr %1026[%1069] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1067 = llvm.load %1070 : !llvm.ptr -> i64
%1072 = arith.constant 6 : i32
%1073 = arith.extsi %1072 : i32 to i64
%1074 = llvm.getelementptr %1026[%1073] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1071 = llvm.load %1074 : !llvm.ptr -> i64
%1076 = arith.constant 10 : i32
%1077 = arith.constant 2 : i32
%1078 = llvm.mlir.addressof @K : !llvm.ptr
%1079 = llvm.load %1078 : !llvm.ptr -> i64
%1081 = arith.extsi %1077 : i32 to i64
%1080 = arith.muli %1081, %1079 : i64
%1082 = arith.constant 2 : i32
%1084 = arith.extsi %1082 : i32 to i64
%1083 = arith.subi %1080, %1084 : i64
%1085 = arith.extsi %1076 : i32 to i64
%1075 = func.call @powmod(%1085, %1083) : (i64, i64) -> i64
%1086 = arith.muli %1075, %1020 : i64
%1087 = llvm.mlir.addressof @M : !llvm.ptr
%1088 = llvm.load %1087 : !llvm.ptr -> i64
%1089 = arith.remsi %1086, %1088 : i64
%1090 = arith.muli %1063, %1063 : i64
%1091 = llvm.mlir.addressof @M : !llvm.ptr
%1092 = llvm.load %1091 : !llvm.ptr -> i64
%1093 = arith.remsi %1090, %1092 : i64
%1094 = arith.muli %1089, %1093 : i64
%1095 = llvm.mlir.addressof @M : !llvm.ptr
%1096 = llvm.load %1095 : !llvm.ptr -> i64
%1097 = arith.remsi %1094, %1096 : i64
%1098 = arith.constant 10 : i32
%1100 = arith.extsi %1098 : i32 to i64
%1099 = arith.muli %1100, %1047 : i64
%1101 = arith.constant 1 : i32
%1103 = arith.extsi %1101 : i32 to i64
%1102 = arith.addi %1099, %1103 : i64
%1104 = llvm.mlir.addressof @M : !llvm.ptr
%1105 = llvm.load %1104 : !llvm.ptr -> i64
%1106 = arith.remsi %1102, %1105 : i64
%1107 = arith.muli %1106, %1106 : i64
%1108 = llvm.mlir.addressof @M : !llvm.ptr
%1109 = llvm.load %1108 : !llvm.ptr -> i64
%1110 = arith.remsi %1107, %1109 : i64
%1111 = arith.constant 100 : i32
%1113 = arith.extsi %1111 : i32 to i64
%1112 = arith.muli %1113, %1059 : i64
%1114 = llvm.mlir.addressof @M : !llvm.ptr
%1115 = llvm.load %1114 : !llvm.ptr -> i64
%1116 = arith.remsi %1112, %1115 : i64
%1117 = arith.constant 20 : i32
%1119 = arith.extsi %1117 : i32 to i64
%1118 = arith.muli %1119, %1055 : i64
%1120 = llvm.mlir.addressof @M : !llvm.ptr
%1121 = llvm.load %1120 : !llvm.ptr -> i64
%1122 = arith.remsi %1118, %1121 : i64
%1123 = arith.addi %1116, %1122 : i64
%1124 = arith.addi %1123, %1051 : i64
%1125 = llvm.mlir.addressof @M : !llvm.ptr
%1126 = llvm.load %1125 : !llvm.ptr -> i64
%1127 = arith.remsi %1124, %1126 : i64
%1128 = arith.muli %1075, %1127 : i64
%1129 = llvm.mlir.addressof @M : !llvm.ptr
%1130 = llvm.load %1129 : !llvm.ptr -> i64
%1131 = arith.remsi %1128, %1130 : i64
%1132 = arith.muli %1020, %1071 : i64
%1133 = llvm.mlir.addressof @M : !llvm.ptr
%1134 = llvm.load %1133 : !llvm.ptr -> i64
%1135 = arith.remsi %1132, %1134 : i64
%1136 = arith.constant 2 : i32
%1138 = arith.extsi %1136 : i32 to i64
%1137 = arith.muli %1138, %1067 : i64
%1139 = llvm.mlir.addressof @M : !llvm.ptr
%1140 = llvm.load %1139 : !llvm.ptr -> i64
%1141 = arith.remsi %1137, %1140 : i64
%1143 = llvm.mlir.addressof @K : !llvm.ptr
%1144 = llvm.load %1143 : !llvm.ptr -> i64
%1145 = arith.constant 2 : i32
%1147 = arith.extsi %1145 : i32 to i64
%1146 = arith.subi %1144, %1147 : i64
%1142 = func.call @pair_sum(%1014, %1146) : (i64, i64) -> i64
%1148 = arith.constant 100 : i32
%1150 = arith.extsi %1148 : i32 to i64
%1149 = arith.muli %1142, %1150 : i64
%1151 = llvm.mlir.addressof @M : !llvm.ptr
%1152 = llvm.load %1151 : !llvm.ptr -> i64
%1153 = arith.remsi %1149, %1152 : i64
%1155 = arith.constant 10 : i32
%1156 = llvm.mlir.addressof @K : !llvm.ptr
%1157 = llvm.load %1156 : !llvm.ptr -> i64
%1158 = arith.constant 2 : i32
%1160 = arith.extsi %1158 : i32 to i64
%1159 = arith.subi %1157, %1160 : i64
%1161 = arith.extsi %1155 : i32 to i64
%1154 = func.call @pair_sum(%1161, %1159) : (i64, i64) -> i64
%1162 = arith.muli %1154, %1020 : i64
%1163 = llvm.mlir.addressof @M : !llvm.ptr
%1164 = llvm.load %1163 : !llvm.ptr -> i64
%1165 = arith.remsi %1162, %1164 : i64
%1167 = arith.constant 99 : i32
%1168 = arith.extsi %1167 : i32 to i64
%1166 = func.call @inv_mod(%1168) : (i64) -> i64
%1169 = arith.muli %1075, %1153 : i64
%1170 = llvm.mlir.addressof @M : !llvm.ptr
%1171 = llvm.load %1170 : !llvm.ptr -> i64
%1172 = arith.remsi %1169, %1171 : i64
%1173 = arith.constant 10000 : i32
%1175 = arith.extsi %1173 : i32 to i64
%1174 = arith.muli %1175, %1165 : i64
%1176 = llvm.mlir.addressof @M : !llvm.ptr
%1177 = llvm.load %1176 : !llvm.ptr -> i64
%1178 = arith.remsi %1174, %1177 : i64
%1179 = arith.subi %1172, %1178 : i64
%1180 = llvm.mlir.addressof @M : !llvm.ptr
%1181 = llvm.load %1180 : !llvm.ptr -> i64
%1182 = arith.addi %1179, %1181 : i64
%1183 = llvm.mlir.addressof @M : !llvm.ptr
%1184 = llvm.load %1183 : !llvm.ptr -> i64
%1185 = arith.remsi %1182, %1184 : i64
%1186 = arith.muli %1166, %1185 : i64
%1187 = llvm.mlir.addressof @M : !llvm.ptr
%1188 = llvm.load %1187 : !llvm.ptr -> i64
%1189 = arith.remsi %1186, %1188 : i64
%1190 = arith.constant 2 : i32
%1192 = arith.extsi %1190 : i32 to i64
%1191 = arith.muli %1192, %1014 : i64
%1193 = llvm.mlir.addressof @M : !llvm.ptr
%1194 = llvm.load %1193 : !llvm.ptr -> i64
%1195 = arith.remsi %1191, %1194 : i64
%1196 = arith.muli %1195, %1189 : i64
%1197 = llvm.mlir.addressof @M : !llvm.ptr
%1198 = llvm.load %1197 : !llvm.ptr -> i64
%1199 = arith.remsi %1196, %1198 : i64
%1200 = arith.addi %1097, %1110 : i64
%1201 = llvm.mlir.addressof @M : !llvm.ptr
%1202 = llvm.load %1201 : !llvm.ptr -> i64
%1203 = arith.remsi %1200, %1202 : i64
%1204 = arith.addi %1131, %1199 : i64
%1205 = llvm.mlir.addressof @M : !llvm.ptr
%1206 = llvm.load %1205 : !llvm.ptr -> i64
%1207 = arith.remsi %1204, %1206 : i64
%1208 = arith.addi %1203, %1207 : i64
%1209 = arith.addi %1141, %1135 : i64
%1210 = llvm.mlir.addressof @M : !llvm.ptr
%1211 = llvm.load %1210 : !llvm.ptr -> i64
%1212 = arith.remsi %1209, %1211 : i64
%1213 = arith.addi %1208, %1212 : i64
%1214 = llvm.mlir.addressof @M : !llvm.ptr
%1215 = llvm.load %1214 : !llvm.ptr -> i64
%1216 = arith.remsi %1213, %1215 : i64
%1217 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1218 = llvm.call @printf(%1217, %1216) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%1021) : (!llvm.ptr) -> ()
func.call @free(%1026) : (!llvm.ptr) -> ()
%1221 = arith.constant 0 : i32
func.return %1221 : i32
}
}