← All problems Problem 977
Count functions f:[n]->[n] with f^{(x)}(y)=f^{(y)}(x), mod 1e9+7. Ported from native C to pure Flow.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)?Space complexity O(1)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 977
# Count functions f:[n]->[n] with f^{(x)}(y)=f^{(y)}(x), mod 1e9+7.
# Ported from native C to pure Flow.
extern {
function malloc(n: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
function mod_pow(a0: i64, e0: i64) -> i64 {
let mut r: i64 = 1
let mut a: i64 = a0 % MOD
if a < 0 { a = a + MOD }
let mut e: i64 = e0
while e > 0 {
if (e & 1) == 1 {
r = (((r as i128) * (a as i128)) % (MOD as i128)) as i64
}
a = (((a as i128) * (a as i128)) % (MOD as i128)) as i64
e = e >> 1
}
return r
}
function main() -> i32 {
let n: i64 = 1000000
if n == 1 {
printf("%lld\n", 1 as i64)
return 0
}
let mut total: i64 = 0
# L = 1 closed form
let m: i64 = n - 2
let sum_q: i128 = ((m as i128) * ((m + 1) as i128) * ((2 * m + 1) as i128)) / 6 + ((m as i128) * ((m + 1) as i128)) / 2
total = ((sum_q % (MOD as i128) + (n as i128)) % (MOD as i128)) as i64
# Preallocate powA buffer
let max_buf: i64 = n / 2 + 3
let powA: ptr<i64> = malloc(max_buf * 8)
let mut L: i64 = 2
while L <= n {
let R: i64 = n - L
if R >= 1 {
let q_full: i64 = (R - 1) / L
let max_a: i64 = q_full + 2
# Precompute a^L mod MOD for a in [1..max_a]
if L == 2 {
let mut a: i64 = 1
while a <= max_a {
powA[a] = (a * a) % MOD
a = a + 1
}
} else {
if L == 3 {
let mut a: i64 = 1
while a <= max_a {
let aa: i64 = (a * a) % MOD
powA[a] = (aa * a) % MOD
a = a + 1
}
} else {
let mut a: i64 = 1
while a <= max_a {
powA[a] = mod_pow(a, L)
a = a + 1
}
}
}
let mut q: i64 = 0
while q < q_full {
let A: i64 = q + 1
let B: i64 = q + 2
let A_L: i64 = powA[A]
let B_L: i64 = powA[B]
let A_L1: i64 = (((A_L as i128) * (A as i128)) % (MOD as i128)) as i64
let term128: i128 = (q as i128) * (A_L as i128) + ((A * A % MOD) as i128) * (B_L as i128) - (B as i128) * (A_L1 as i128)
let mut term: i64 = (term128 % (MOD as i128)) as i64
if term < 0 { term = term + MOD }
total = (total + term) % MOD
q = q + 1
}
# Last partial block for q = q_full
q = q_full
let mm: i64 = (R - 1) - q_full * L
let A: i64 = q + 1
let B: i64 = q + 2
let A_L: i64 = powA[A]
let mut term: i64 = (((q as i128) * (A_L as i128)) % (MOD as i128)) as i64
if mm >= 1 {
let A_L1: i64 = (((A_L as i128) * (A as i128)) % (MOD as i128)) as i64
let exp: i64 = L + 1 - mm
let A_L1_m: i64 = 0
if exp == 1 {
A_L1_m = A % MOD
} else {
if exp == 2 {
A_L1_m = (A * A) % MOD
} else {
if exp == 3 {
A_L1_m = (((A * A % MOD) as i128) * (A as i128) % (MOD as i128)) as i64
} else {
A_L1_m = mod_pow(A, exp)
}
}
}
let B_m: i64 = 0
if mm == 1 {
B_m = B % MOD
} else {
if mm == 2 {
B_m = (B * B) % MOD
} else {
if mm == 3 {
B_m = (((B * B % MOD) as i128) * (B as i128) % (MOD as i128)) as i64
} else {
B_m = mod_pow(B, mm)
}
}
}
let mut inner: i64 = ((((A_L1_m as i128) * (B_m as i128) % (MOD as i128) - (A_L1 as i128)) % (MOD as i128))) as i64
if inner < 0 { inner = inner + MOD }
term = (((term as i128) + ((B as i128) * (inner as i128) % (MOD as i128)))) as i64 % MOD
}
total = (total + term) % MOD
}
# mu = 0 contribution for rem = R
let q: i64 = R / L
let r: i64 = R - q * L
let A: i64 = q + 1
let B: i64 = q + 2
let base: i64 = 0
if r == 0 {
base = mod_pow(A, L)
} else {
base = (((mod_pow(A, L - r) as i128) * (mod_pow(B, r) as i128)) % (MOD as i128)) as i64
}
total = (total + base) % MOD
L = L + 1
}
free(powA)
printf("%lld\n", total % MOD)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t mod_pow_i64_i64(int64_t a0, int64_t e0);
int32_t main(void);
static const int64_t MOD = 1000000007;
int64_t mod_pow_i64_i64(int64_t a0, int64_t e0) {
int64_t r = 1;
int64_t a = FLOW_CHECKED_MOD((a0), (MOD));
if (a < 0) {
a = (a + MOD);
}
int64_t e = e0;
while (e > 0) {
if ((e & 1) == 1) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(a)))), (((__int128)(MOD))))));
}
a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(a)))), (((__int128)(MOD))))));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int32_t main(void) {
int64_t n = 1000000;
if (n == 1) {
printf("%lld\n", ((int64_t)(1)));
return 0;
}
int64_t total = 0;
int64_t m = (n - 2);
__int128 sum_q = (FLOW_CHECKED_DIV((((((__int128)(m)) * ((__int128)((m + 1)))) * ((__int128)(((2 * m) + 1))))), (6)) + FLOW_CHECKED_DIV(((((__int128)(m)) * ((__int128)((m + 1))))), (2)));
total = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((sum_q), (((__int128)(MOD)))) + ((__int128)(n)))), (((__int128)(MOD))))));
int64_t max_buf = (FLOW_CHECKED_DIV((n), (2)) + 3);
int64_t* powA = (int64_t*)(malloc((max_buf * 8)));
int64_t L = 2;
while (L <= n) {
int64_t R = (n - L);
if (R >= 1) {
int64_t q_full = FLOW_CHECKED_DIV(((R - 1)), (L));
int64_t max_a = (q_full + 2);
if (L == 2) {
int64_t a = 1;
while (a <= max_a) {
powA[a] = FLOW_CHECKED_MOD(((a * a)), (MOD));
a = (a + 1);
}
} else {
if (L == 3) {
int64_t a = 1;
while (a <= max_a) {
int64_t aa = FLOW_CHECKED_MOD(((a * a)), (MOD));
powA[a] = FLOW_CHECKED_MOD(((aa * a)), (MOD));
a = (a + 1);
}
} else {
int64_t a = 1;
while (a <= max_a) {
powA[a] = mod_pow_i64_i64(a, L);
a = (a + 1);
}
}
}
int64_t q = 0;
while (q < q_full) {
int64_t A = (q + 1);
int64_t B = (q + 2);
int64_t A_L = powA[A];
int64_t B_L = powA[B];
int64_t A_L1 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(A_L)) * ((__int128)(A)))), (((__int128)(MOD))))));
__int128 term128 = (((((__int128)(q)) * ((__int128)(A_L))) + (((__int128)(FLOW_CHECKED_MOD(((A * A)), (MOD)))) * ((__int128)(B_L)))) - (((__int128)(B)) * ((__int128)(A_L1))));
int64_t term = ((int64_t)(FLOW_CHECKED_MOD((term128), (((__int128)(MOD))))));
if (term < 0) {
term = (term + MOD);
}
total = FLOW_CHECKED_MOD(((total + term)), (MOD));
q = (q + 1);
}
q = q_full;
int64_t mm = ((R - 1) - (q_full * L));
int64_t A = (q + 1);
int64_t B = (q + 2);
int64_t A_L = powA[A];
int64_t term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(q)) * ((__int128)(A_L)))), (((__int128)(MOD))))));
if (mm >= 1) {
int64_t A_L1 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(A_L)) * ((__int128)(A)))), (((__int128)(MOD))))));
int64_t exp = ((L + 1) - mm);
int64_t A_L1_m = 0;
if (exp == 1) {
A_L1_m = FLOW_CHECKED_MOD((A), (MOD));
} else {
if (exp == 2) {
A_L1_m = FLOW_CHECKED_MOD(((A * A)), (MOD));
} else {
if (exp == 3) {
A_L1_m = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD(((A * A)), (MOD)))) * ((__int128)(A)))), (((__int128)(MOD))))));
} else {
A_L1_m = mod_pow_i64_i64(A, exp);
}
}
}
int64_t B_m = 0;
if (mm == 1) {
B_m = FLOW_CHECKED_MOD((B), (MOD));
} else {
if (mm == 2) {
B_m = FLOW_CHECKED_MOD(((B * B)), (MOD));
} else {
if (mm == 3) {
B_m = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD(((B * B)), (MOD)))) * ((__int128)(B)))), (((__int128)(MOD))))));
} else {
B_m = mod_pow_i64_i64(B, mm);
}
}
}
int64_t inner = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((((__int128)(A_L1_m)) * ((__int128)(B_m)))), (((__int128)(MOD)))) - ((__int128)(A_L1)))), (((__int128)(MOD))))));
if (inner < 0) {
inner = (inner + MOD);
}
term = FLOW_CHECKED_MOD((((int64_t)((((__int128)(term)) + FLOW_CHECKED_MOD(((((__int128)(B)) * ((__int128)(inner)))), (((__int128)(MOD)))))))), (MOD));
}
total = FLOW_CHECKED_MOD(((total + term)), (MOD));
}
int64_t q = FLOW_CHECKED_DIV((R), (L));
int64_t r = (R - (q * L));
int64_t A = (q + 1);
int64_t B = (q + 2);
int64_t base = 0;
if (r == 0) {
base = mod_pow_i64_i64(A, L);
} else {
base = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(mod_pow_i64_i64(A, (L - r)))) * ((__int128)(mod_pow_i64_i64(B, r))))), (((__int128)(MOD))))));
}
total = FLOW_CHECKED_MOD(((total + base)), (MOD));
L = (L + 1);
}
free(powA);
printf("%lld\n", FLOW_CHECKED_MOD((total), (MOD)));
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 @malloc(i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
func.func @mod_pow(%arg0: i64, %arg1: i64) -> i64 {
%0 = arith.constant 1 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = llvm.mlir.addressof @MOD : !llvm.ptr
%5 = llvm.load %4 : !llvm.ptr -> i64
%6 = arith.remsi %arg0, %5 : i64
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %6, %8 : i64, !llvm.ptr
%9 = llvm.load %8 : !llvm.ptr -> i64
%10 = arith.constant 0 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.cmpi slt, %9, %12 : i64
cf.cond_br %11, ^bb0, ^bb1
^bb0:
%13 = llvm.load %8 : !llvm.ptr -> i64
%14 = llvm.mlir.addressof @MOD : !llvm.ptr
%15 = llvm.load %14 : !llvm.ptr -> i64
%16 = arith.addi %13, %15 : i64
llvm.store %16, %8 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%17 = llvm.mlir.constant(1 : i64) : i64
%18 = llvm.alloca %17 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %18 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%19 = llvm.load %18 : !llvm.ptr -> i64
%20 = arith.constant 0 : i32
%22 = arith.extsi %20 : i32 to i64
%21 = arith.cmpi sgt, %19, %22 : i64
cf.cond_br %21, ^bb4, ^bb5
^bb4:
%23 = llvm.load %18 : !llvm.ptr -> i64
%24 = arith.constant 1 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.andi %23, %26 : i64
%27 = arith.constant 1 : i32
%29 = arith.extsi %27 : i32 to i64
%28 = arith.cmpi eq, %25, %29 : i64
cf.cond_br %28, ^bb6, ^bb7
^bb6:
%30 = llvm.load %3 : !llvm.ptr -> i64
%31 = arith.extsi %30 : i64 to i128
%32 = llvm.load %8 : !llvm.ptr -> i64
%33 = arith.extsi %32 : i64 to i128
%35 = arith.trunci %31 : i128 to i64
%36 = arith.trunci %33 : i128 to i64
%34 = arith.muli %35, %36 : i64
%37 = llvm.mlir.addressof @MOD : !llvm.ptr
%38 = llvm.load %37 : !llvm.ptr -> i64
%39 = arith.extsi %38 : i64 to i128
%41 = arith.trunci %39 : i128 to i64
%40 = arith.remsi %34, %41 : i64
llvm.store %40, %3 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%42 = llvm.load %8 : !llvm.ptr -> i64
%43 = arith.extsi %42 : i64 to i128
%44 = llvm.load %8 : !llvm.ptr -> i64
%45 = arith.extsi %44 : i64 to i128
%47 = arith.trunci %43 : i128 to i64
%48 = arith.trunci %45 : i128 to i64
%46 = arith.muli %47, %48 : i64
%49 = llvm.mlir.addressof @MOD : !llvm.ptr
%50 = llvm.load %49 : !llvm.ptr -> i64
%51 = arith.extsi %50 : i64 to i128
%53 = arith.trunci %51 : i128 to i64
%52 = arith.remsi %46, %53 : i64
llvm.store %52, %8 : i64, !llvm.ptr
%54 = llvm.load %18 : !llvm.ptr -> i64
%55 = arith.constant 1 : i32
%57 = arith.extsi %55 : i32 to i64
%56 = arith.shrsi %54, %57 : i64
llvm.store %56, %18 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%58 = llvm.load %3 : !llvm.ptr -> i64
func.return %58 : i64
}
func.func @main() -> i32 {
%59 = arith.constant 1000000 : i32
%60 = arith.extsi %59 : i32 to i64
%61 = arith.constant 1 : i32
%63 = arith.extsi %61 : i32 to i64
%62 = arith.cmpi eq, %60, %63 : i64
cf.cond_br %62, ^bb9, ^bb10
^bb9:
%64 = llvm.mlir.addressof @str_0 : !llvm.ptr
%65 = arith.constant 1 : i32
%66 = arith.extsi %65 : i32 to i64
%67 = llvm.call @printf(%64, %66) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%68 = arith.constant 0 : i32
func.return %68 : i32
^bb10:
cf.br ^bb11
^bb11:
%69 = arith.constant 0 : i32
%70 = arith.extsi %69 : i32 to i64
%71 = llvm.mlir.constant(1 : i64) : i64
%72 = llvm.alloca %71 x i64 : (i64) -> !llvm.ptr
llvm.store %70, %72 : i64, !llvm.ptr
%73 = arith.constant 2 : i32
%75 = arith.extsi %73 : i32 to i64
%74 = arith.subi %60, %75 : i64
%76 = arith.extsi %74 : i64 to i128
%77 = arith.constant 1 : i32
%79 = arith.extsi %77 : i32 to i64
%78 = arith.addi %74, %79 : i64
%80 = arith.extsi %78 : i64 to i128
%82 = arith.trunci %76 : i128 to i64
%83 = arith.trunci %80 : i128 to i64
%81 = arith.muli %82, %83 : i64
%84 = arith.constant 2 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.muli %86, %74 : i64
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.addi %85, %89 : i64
%90 = arith.extsi %88 : i64 to i128
%92 = arith.trunci %90 : i128 to i64
%91 = arith.muli %81, %92 : i64
%93 = arith.constant 6 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.divsi %91, %95 : i64
%96 = arith.extsi %74 : i64 to i128
%97 = arith.constant 1 : i32
%99 = arith.extsi %97 : i32 to i64
%98 = arith.addi %74, %99 : i64
%100 = arith.extsi %98 : i64 to i128
%102 = arith.trunci %96 : i128 to i64
%103 = arith.trunci %100 : i128 to i64
%101 = arith.muli %102, %103 : i64
%104 = arith.constant 2 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.divsi %101, %106 : i64
%107 = arith.addi %94, %105 : i64
%108 = arith.extsi %107 : i64 to i128
%109 = llvm.mlir.addressof @MOD : !llvm.ptr
%110 = llvm.load %109 : !llvm.ptr -> i64
%111 = arith.extsi %110 : i64 to i128
%113 = arith.trunci %108 : i128 to i64
%114 = arith.trunci %111 : i128 to i64
%112 = arith.remsi %113, %114 : i64
%115 = arith.extsi %60 : i64 to i128
%117 = arith.trunci %115 : i128 to i64
%116 = arith.addi %112, %117 : i64
%118 = llvm.mlir.addressof @MOD : !llvm.ptr
%119 = llvm.load %118 : !llvm.ptr -> i64
%120 = arith.extsi %119 : i64 to i128
%122 = arith.trunci %120 : i128 to i64
%121 = arith.remsi %116, %122 : i64
llvm.store %121, %72 : i64, !llvm.ptr
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.divsi %60, %125 : i64
%126 = arith.constant 3 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.addi %124, %128 : i64
%130 = arith.constant 8 : i32
%132 = arith.extsi %130 : i32 to i64
%131 = arith.muli %127, %132 : i64
%129 = func.call @malloc(%131) : (i64) -> !llvm.ptr
%133 = arith.constant 2 : i32
%134 = arith.extsi %133 : i32 to i64
%135 = llvm.mlir.constant(1 : i64) : i64
%136 = llvm.alloca %135 x i64 : (i64) -> !llvm.ptr
llvm.store %134, %136 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%137 = llvm.load %136 : !llvm.ptr -> i64
%138 = arith.cmpi sle, %137, %60 : i64
cf.cond_br %138, ^bb13, ^bb14
^bb13:
%139 = llvm.load %136 : !llvm.ptr -> i64
%140 = arith.subi %60, %139 : i64
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.cmpi sge, %140, %143 : i64
cf.cond_br %142, ^bb15, ^bb16
^bb15:
%144 = arith.constant 1 : i32
%146 = arith.extsi %144 : i32 to i64
%145 = arith.subi %140, %146 : i64
%147 = llvm.load %136 : !llvm.ptr -> i64
%148 = arith.divsi %145, %147 : i64
%149 = arith.constant 2 : i32
%151 = arith.extsi %149 : i32 to i64
%150 = arith.addi %148, %151 : i64
%152 = llvm.load %136 : !llvm.ptr -> i64
%153 = arith.constant 2 : i32
%155 = arith.extsi %153 : i32 to i64
%154 = arith.cmpi eq, %152, %155 : i64
cf.cond_br %154, ^bb18, ^bb19
^bb18:
%156 = arith.constant 1 : i32
%157 = arith.extsi %156 : i32 to i64
%158 = llvm.mlir.constant(1 : i64) : i64
%159 = llvm.alloca %158 x i64 : (i64) -> !llvm.ptr
llvm.store %157, %159 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%160 = llvm.load %159 : !llvm.ptr -> i64
%161 = arith.cmpi sle, %160, %150 : i64
cf.cond_br %161, ^bb22, ^bb23
^bb22:
%162 = llvm.load %159 : !llvm.ptr -> i64
%163 = llvm.load %159 : !llvm.ptr -> i64
%164 = arith.muli %162, %163 : i64
%165 = llvm.mlir.addressof @MOD : !llvm.ptr
%166 = llvm.load %165 : !llvm.ptr -> i64
%167 = arith.remsi %164, %166 : i64
%168 = llvm.load %159 : !llvm.ptr -> i64
%169 = llvm.getelementptr %129[%168] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %167, %169 : i64, !llvm.ptr
%170 = llvm.load %159 : !llvm.ptr -> i64
%171 = arith.constant 1 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %159 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
cf.br ^bb20
^bb19:
%174 = llvm.load %136 : !llvm.ptr -> i64
%175 = arith.constant 3 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.cmpi eq, %174, %177 : i64
cf.cond_br %176, ^bb24, ^bb25
^bb24:
%178 = arith.constant 1 : i32
%179 = arith.extsi %178 : i32 to i64
%180 = llvm.mlir.constant(1 : i64) : i64
%181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
llvm.store %179, %181 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%182 = llvm.load %181 : !llvm.ptr -> i64
%183 = arith.cmpi sle, %182, %150 : i64
cf.cond_br %183, ^bb28, ^bb29
^bb28:
%184 = llvm.load %181 : !llvm.ptr -> i64
%185 = llvm.load %181 : !llvm.ptr -> i64
%186 = arith.muli %184, %185 : i64
%187 = llvm.mlir.addressof @MOD : !llvm.ptr
%188 = llvm.load %187 : !llvm.ptr -> i64
%189 = arith.remsi %186, %188 : i64
%190 = llvm.load %181 : !llvm.ptr -> i64
%191 = arith.muli %189, %190 : i64
%192 = llvm.mlir.addressof @MOD : !llvm.ptr
%193 = llvm.load %192 : !llvm.ptr -> i64
%194 = arith.remsi %191, %193 : i64
%195 = llvm.load %181 : !llvm.ptr -> i64
%196 = llvm.getelementptr %129[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %194, %196 : i64, !llvm.ptr
%197 = llvm.load %181 : !llvm.ptr -> i64
%198 = arith.constant 1 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.addi %197, %200 : i64
llvm.store %199, %181 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
cf.br ^bb26
^bb25:
%201 = arith.constant 1 : i32
%202 = arith.extsi %201 : i32 to i64
%203 = llvm.mlir.constant(1 : i64) : i64
%204 = llvm.alloca %203 x i64 : (i64) -> !llvm.ptr
llvm.store %202, %204 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%205 = llvm.load %204 : !llvm.ptr -> i64
%206 = arith.cmpi sle, %205, %150 : i64
cf.cond_br %206, ^bb31, ^bb32
^bb31:
%208 = llvm.load %204 : !llvm.ptr -> i64
%209 = llvm.load %136 : !llvm.ptr -> i64
%207 = func.call @mod_pow(%208, %209) : (i64, i64) -> i64
%210 = llvm.load %204 : !llvm.ptr -> i64
%211 = llvm.getelementptr %129[%210] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %207, %211 : i64, !llvm.ptr
%212 = llvm.load %204 : !llvm.ptr -> i64
%213 = arith.constant 1 : i32
%215 = arith.extsi %213 : i32 to i64
%214 = arith.addi %212, %215 : i64
llvm.store %214, %204 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
cf.br ^bb26
^bb26:
cf.br ^bb20
^bb20:
%216 = arith.constant 0 : i32
%217 = arith.extsi %216 : i32 to i64
%218 = llvm.mlir.constant(1 : i64) : i64
%219 = llvm.alloca %218 x i64 : (i64) -> !llvm.ptr
llvm.store %217, %219 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%220 = llvm.load %219 : !llvm.ptr -> i64
%221 = arith.cmpi slt, %220, %148 : i64
cf.cond_br %221, ^bb34, ^bb35
^bb34:
%222 = llvm.load %219 : !llvm.ptr -> i64
%223 = arith.constant 1 : i32
%225 = arith.extsi %223 : i32 to i64
%224 = arith.addi %222, %225 : i64
%226 = llvm.load %219 : !llvm.ptr -> i64
%227 = arith.constant 2 : i32
%229 = arith.extsi %227 : i32 to i64
%228 = arith.addi %226, %229 : i64
%231 = llvm.getelementptr %129[%224] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%230 = llvm.load %231 : !llvm.ptr -> i64
%233 = llvm.getelementptr %129[%228] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%232 = llvm.load %233 : !llvm.ptr -> i64
%234 = arith.extsi %230 : i64 to i128
%235 = arith.extsi %224 : i64 to i128
%237 = arith.trunci %234 : i128 to i64
%238 = arith.trunci %235 : i128 to i64
%236 = arith.muli %237, %238 : i64
%239 = llvm.mlir.addressof @MOD : !llvm.ptr
%240 = llvm.load %239 : !llvm.ptr -> i64
%241 = arith.extsi %240 : i64 to i128
%243 = arith.trunci %241 : i128 to i64
%242 = arith.remsi %236, %243 : i64
%244 = llvm.load %219 : !llvm.ptr -> i64
%245 = arith.extsi %244 : i64 to i128
%246 = arith.extsi %230 : i64 to i128
%248 = arith.trunci %245 : i128 to i64
%249 = arith.trunci %246 : i128 to i64
%247 = arith.muli %248, %249 : i64
%250 = arith.muli %224, %224 : i64
%251 = llvm.mlir.addressof @MOD : !llvm.ptr
%252 = llvm.load %251 : !llvm.ptr -> i64
%253 = arith.remsi %250, %252 : i64
%254 = arith.extsi %253 : i64 to i128
%255 = arith.extsi %232 : i64 to i128
%257 = arith.trunci %254 : i128 to i64
%258 = arith.trunci %255 : i128 to i64
%256 = arith.muli %257, %258 : i64
%259 = arith.addi %247, %256 : i64
%260 = arith.extsi %228 : i64 to i128
%261 = arith.extsi %242 : i64 to i128
%263 = arith.trunci %260 : i128 to i64
%264 = arith.trunci %261 : i128 to i64
%262 = arith.muli %263, %264 : i64
%265 = arith.subi %259, %262 : i64
%266 = arith.extsi %265 : i64 to i128
%267 = llvm.mlir.addressof @MOD : !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> i64
%269 = arith.extsi %268 : i64 to i128
%271 = arith.trunci %266 : i128 to i64
%272 = arith.trunci %269 : i128 to i64
%270 = arith.remsi %271, %272 : i64
%273 = llvm.mlir.constant(1 : i64) : i64
%274 = llvm.alloca %273 x i64 : (i64) -> !llvm.ptr
llvm.store %270, %274 : i64, !llvm.ptr
%275 = llvm.load %274 : !llvm.ptr -> i64
%276 = arith.constant 0 : i32
%278 = arith.extsi %276 : i32 to i64
%277 = arith.cmpi slt, %275, %278 : i64
cf.cond_br %277, ^bb36, ^bb37
^bb36:
%279 = llvm.load %274 : !llvm.ptr -> i64
%280 = llvm.mlir.addressof @MOD : !llvm.ptr
%281 = llvm.load %280 : !llvm.ptr -> i64
%282 = arith.addi %279, %281 : i64
llvm.store %282, %274 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%283 = llvm.load %72 : !llvm.ptr -> i64
%284 = llvm.load %274 : !llvm.ptr -> i64
%285 = arith.addi %283, %284 : i64
%286 = llvm.mlir.addressof @MOD : !llvm.ptr
%287 = llvm.load %286 : !llvm.ptr -> i64
%288 = arith.remsi %285, %287 : i64
llvm.store %288, %72 : i64, !llvm.ptr
%289 = llvm.load %219 : !llvm.ptr -> i64
%290 = arith.constant 1 : i32
%292 = arith.extsi %290 : i32 to i64
%291 = arith.addi %289, %292 : i64
llvm.store %291, %219 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
llvm.store %148, %219 : i64, !llvm.ptr
%293 = arith.constant 1 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.subi %140, %295 : i64
%296 = llvm.load %136 : !llvm.ptr -> i64
%297 = arith.muli %148, %296 : i64
%298 = arith.subi %294, %297 : i64
%299 = llvm.load %219 : !llvm.ptr -> i64
%300 = arith.constant 1 : i32
%302 = arith.extsi %300 : i32 to i64
%301 = arith.addi %299, %302 : i64
%303 = llvm.load %219 : !llvm.ptr -> i64
%304 = arith.constant 2 : i32
%306 = arith.extsi %304 : i32 to i64
%305 = arith.addi %303, %306 : i64
%308 = llvm.getelementptr %129[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%307 = llvm.load %308 : !llvm.ptr -> i64
%309 = llvm.load %219 : !llvm.ptr -> i64
%310 = arith.extsi %309 : i64 to i128
%311 = arith.extsi %307 : i64 to i128
%313 = arith.trunci %310 : i128 to i64
%314 = arith.trunci %311 : i128 to i64
%312 = arith.muli %313, %314 : i64
%315 = llvm.mlir.addressof @MOD : !llvm.ptr
%316 = llvm.load %315 : !llvm.ptr -> i64
%317 = arith.extsi %316 : i64 to i128
%319 = arith.trunci %317 : i128 to i64
%318 = arith.remsi %312, %319 : i64
%320 = llvm.mlir.constant(1 : i64) : i64
%321 = llvm.alloca %320 x i64 : (i64) -> !llvm.ptr
llvm.store %318, %321 : i64, !llvm.ptr
%322 = arith.constant 1 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.cmpi sge, %298, %324 : i64
cf.cond_br %323, ^bb39, ^bb40
^bb39:
%325 = arith.extsi %307 : i64 to i128
%326 = arith.extsi %301 : i64 to i128
%328 = arith.trunci %325 : i128 to i64
%329 = arith.trunci %326 : i128 to i64
%327 = arith.muli %328, %329 : i64
%330 = llvm.mlir.addressof @MOD : !llvm.ptr
%331 = llvm.load %330 : !llvm.ptr -> i64
%332 = arith.extsi %331 : i64 to i128
%334 = arith.trunci %332 : i128 to i64
%333 = arith.remsi %327, %334 : i64
%335 = llvm.load %136 : !llvm.ptr -> i64
%336 = arith.constant 1 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.addi %335, %338 : i64
%339 = arith.subi %337, %298 : i64
%340 = arith.constant 0 : i32
%341 = arith.extsi %340 : i32 to i64
%342 = arith.constant 1 : i32
%344 = arith.extsi %342 : i32 to i64
%343 = arith.cmpi eq, %339, %344 : i64
cf.cond_br %343, ^bb42, ^bb43
^bb42:
%345 = llvm.mlir.addressof @MOD : !llvm.ptr
%346 = llvm.load %345 : !llvm.ptr -> i64
%347 = arith.remsi %301, %346 : i64
cf.br ^bb44(%347 : i64)
^bb43:
%348 = arith.constant 2 : i32
%350 = arith.extsi %348 : i32 to i64
%349 = arith.cmpi eq, %339, %350 : i64
cf.cond_br %349, ^bb45, ^bb46
^bb45:
%351 = arith.muli %301, %301 : i64
%352 = llvm.mlir.addressof @MOD : !llvm.ptr
%353 = llvm.load %352 : !llvm.ptr -> i64
%354 = arith.remsi %351, %353 : i64
cf.br ^bb47(%354 : i64)
^bb46:
%355 = arith.constant 3 : i32
%357 = arith.extsi %355 : i32 to i64
%356 = arith.cmpi eq, %339, %357 : i64
%358 = scf.if %356 -> (i64) {
%359 = arith.muli %301, %301 : i64
%360 = llvm.mlir.addressof @MOD : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> i64
%362 = arith.remsi %359, %361 : i64
%363 = arith.extsi %362 : i64 to i128
%364 = arith.extsi %301 : i64 to i128
%366 = arith.trunci %363 : i128 to i64
%367 = arith.trunci %364 : i128 to i64
%365 = arith.muli %366, %367 : i64
%368 = llvm.mlir.addressof @MOD : !llvm.ptr
%369 = llvm.load %368 : !llvm.ptr -> i64
%370 = arith.extsi %369 : i64 to i128
%372 = arith.trunci %370 : i128 to i64
%371 = arith.remsi %365, %372 : i64
scf.yield %371 : i64
} else {
%373 = func.call @mod_pow(%301, %339) : (i64, i64) -> i64
scf.yield %373 : i64
}
cf.br ^bb47(%358 : i64)
^bb47(%374: i64):
cf.br ^bb44(%374 : i64)
^bb44(%375: i64):
%376 = arith.constant 0 : i32
%377 = arith.extsi %376 : i32 to i64
%378 = arith.constant 1 : i32
%380 = arith.extsi %378 : i32 to i64
%379 = arith.cmpi eq, %298, %380 : i64
cf.cond_br %379, ^bb48, ^bb49
^bb48:
%381 = llvm.mlir.addressof @MOD : !llvm.ptr
%382 = llvm.load %381 : !llvm.ptr -> i64
%383 = arith.remsi %305, %382 : i64
cf.br ^bb50(%383 : i64)
^bb49:
%384 = arith.constant 2 : i32
%386 = arith.extsi %384 : i32 to i64
%385 = arith.cmpi eq, %298, %386 : i64
cf.cond_br %385, ^bb51, ^bb52
^bb51:
%387 = arith.muli %305, %305 : i64
%388 = llvm.mlir.addressof @MOD : !llvm.ptr
%389 = llvm.load %388 : !llvm.ptr -> i64
%390 = arith.remsi %387, %389 : i64
cf.br ^bb53(%390 : i64)
^bb52:
%391 = arith.constant 3 : i32
%393 = arith.extsi %391 : i32 to i64
%392 = arith.cmpi eq, %298, %393 : i64
%394 = scf.if %392 -> (i64) {
%395 = arith.muli %305, %305 : i64
%396 = llvm.mlir.addressof @MOD : !llvm.ptr
%397 = llvm.load %396 : !llvm.ptr -> i64
%398 = arith.remsi %395, %397 : i64
%399 = arith.extsi %398 : i64 to i128
%400 = arith.extsi %305 : i64 to i128
%402 = arith.trunci %399 : i128 to i64
%403 = arith.trunci %400 : i128 to i64
%401 = arith.muli %402, %403 : i64
%404 = llvm.mlir.addressof @MOD : !llvm.ptr
%405 = llvm.load %404 : !llvm.ptr -> i64
%406 = arith.extsi %405 : i64 to i128
%408 = arith.trunci %406 : i128 to i64
%407 = arith.remsi %401, %408 : i64
scf.yield %407 : i64
} else {
%409 = func.call @mod_pow(%305, %298) : (i64, i64) -> i64
scf.yield %409 : i64
}
cf.br ^bb53(%394 : i64)
^bb53(%410: i64):
cf.br ^bb50(%410 : i64)
^bb50(%411: i64):
%412 = arith.extsi %375 : i64 to i128
%413 = arith.extsi %411 : i64 to i128
%415 = arith.trunci %412 : i128 to i64
%416 = arith.trunci %413 : i128 to i64
%414 = arith.muli %415, %416 : i64
%417 = llvm.mlir.addressof @MOD : !llvm.ptr
%418 = llvm.load %417 : !llvm.ptr -> i64
%419 = arith.extsi %418 : i64 to i128
%421 = arith.trunci %419 : i128 to i64
%420 = arith.remsi %414, %421 : i64
%422 = arith.extsi %333 : i64 to i128
%424 = arith.trunci %422 : i128 to i64
%423 = arith.subi %420, %424 : i64
%425 = llvm.mlir.addressof @MOD : !llvm.ptr
%426 = llvm.load %425 : !llvm.ptr -> i64
%427 = arith.extsi %426 : i64 to i128
%429 = arith.trunci %427 : i128 to i64
%428 = arith.remsi %423, %429 : i64
%430 = llvm.mlir.constant(1 : i64) : i64
%431 = llvm.alloca %430 x i64 : (i64) -> !llvm.ptr
llvm.store %428, %431 : i64, !llvm.ptr
%432 = llvm.load %431 : !llvm.ptr -> i64
%433 = arith.constant 0 : i32
%435 = arith.extsi %433 : i32 to i64
%434 = arith.cmpi slt, %432, %435 : i64
cf.cond_br %434, ^bb54, ^bb55
^bb54:
%436 = llvm.load %431 : !llvm.ptr -> i64
%437 = llvm.mlir.addressof @MOD : !llvm.ptr
%438 = llvm.load %437 : !llvm.ptr -> i64
%439 = arith.addi %436, %438 : i64
llvm.store %439, %431 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%440 = llvm.load %321 : !llvm.ptr -> i64
%441 = arith.extsi %440 : i64 to i128
%442 = arith.extsi %305 : i64 to i128
%443 = llvm.load %431 : !llvm.ptr -> i64
%444 = arith.extsi %443 : i64 to i128
%446 = arith.trunci %442 : i128 to i64
%447 = arith.trunci %444 : i128 to i64
%445 = arith.muli %446, %447 : i64
%448 = llvm.mlir.addressof @MOD : !llvm.ptr
%449 = llvm.load %448 : !llvm.ptr -> i64
%450 = arith.extsi %449 : i64 to i128
%452 = arith.trunci %450 : i128 to i64
%451 = arith.remsi %445, %452 : i64
%454 = arith.trunci %441 : i128 to i64
%453 = arith.addi %454, %451 : i64
%455 = llvm.mlir.addressof @MOD : !llvm.ptr
%456 = llvm.load %455 : !llvm.ptr -> i64
%457 = arith.remsi %453, %456 : i64
llvm.store %457, %321 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%458 = llvm.load %72 : !llvm.ptr -> i64
%459 = llvm.load %321 : !llvm.ptr -> i64
%460 = arith.addi %458, %459 : i64
%461 = llvm.mlir.addressof @MOD : !llvm.ptr
%462 = llvm.load %461 : !llvm.ptr -> i64
%463 = arith.remsi %460, %462 : i64
llvm.store %463, %72 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%464 = llvm.load %136 : !llvm.ptr -> i64
%465 = arith.divsi %140, %464 : i64
%466 = llvm.load %136 : !llvm.ptr -> i64
%467 = arith.muli %465, %466 : i64
%468 = arith.subi %140, %467 : i64
%469 = arith.constant 1 : i32
%471 = arith.extsi %469 : i32 to i64
%470 = arith.addi %465, %471 : i64
%472 = arith.constant 2 : i32
%474 = arith.extsi %472 : i32 to i64
%473 = arith.addi %465, %474 : i64
%475 = arith.constant 0 : i32
%476 = arith.extsi %475 : i32 to i64
%477 = arith.constant 0 : i32
%479 = arith.extsi %477 : i32 to i64
%478 = arith.cmpi eq, %468, %479 : i64
%480 = scf.if %478 -> (i64) {
%482 = llvm.load %136 : !llvm.ptr -> i64
%481 = func.call @mod_pow(%470, %482) : (i64, i64) -> i64
scf.yield %481 : i64
} else {
%484 = llvm.load %136 : !llvm.ptr -> i64
%485 = arith.subi %484, %468 : i64
%483 = func.call @mod_pow(%470, %485) : (i64, i64) -> i64
%486 = arith.extsi %483 : i64 to i128
%487 = func.call @mod_pow(%473, %468) : (i64, i64) -> i64
%488 = arith.extsi %487 : i64 to i128
%490 = arith.trunci %486 : i128 to i64
%491 = arith.trunci %488 : i128 to i64
%489 = arith.muli %490, %491 : i64
%492 = llvm.mlir.addressof @MOD : !llvm.ptr
%493 = llvm.load %492 : !llvm.ptr -> i64
%494 = arith.extsi %493 : i64 to i128
%496 = arith.trunci %494 : i128 to i64
%495 = arith.remsi %489, %496 : i64
scf.yield %495 : i64
}
%497 = llvm.load %72 : !llvm.ptr -> i64
%498 = arith.addi %497, %480 : i64
%499 = llvm.mlir.addressof @MOD : !llvm.ptr
%500 = llvm.load %499 : !llvm.ptr -> i64
%501 = arith.remsi %498, %500 : i64
llvm.store %501, %72 : i64, !llvm.ptr
%502 = llvm.load %136 : !llvm.ptr -> i64
%503 = arith.constant 1 : i32
%505 = arith.extsi %503 : i32 to i64
%504 = arith.addi %502, %505 : i64
llvm.store %504, %136 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
func.call @free(%129) : (!llvm.ptr) -> ()
%507 = llvm.mlir.addressof @str_0 : !llvm.ptr
%508 = llvm.load %72 : !llvm.ptr -> i64
%509 = llvm.mlir.addressof @MOD : !llvm.ptr
%510 = llvm.load %509 : !llvm.ptr -> i64
%511 = arith.remsi %508, %510 : i64
%512 = llvm.call @printf(%507, %511) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%513 = arith.constant 0 : i32
func.return %513 : i32
}
}