← All problems Problem 811
H(t, r) = A((2^t + 1)^r) mod 1000062031 with t = 10^14 + 31, r = 62.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)?Space complexity O(n)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 811: Bitwise Recursion
# H(t, r) = A((2^t + 1)^r) mod 1000062031
# with t = 10^14 + 31, r = 62.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000062031
# Positions of 1-bits in (2^t + 1)^r using the binomial block method.
# Assumes t >= max_binom_bitlen(r) so blocks don't overlap.
# Returns positions in increasing order.
function one_positions_via_binom(t: i64, r: i32, pos_out: ptr<i64>) -> i32 {
let mut cnt: i32 = 0
let mut c: i128 = 1 as i128
let mut k: i32 = 0
while k <= r {
let mut x: i128 = c
while x != (0 as i128) {
let lsb: i128 = x & ((0 as i128) - x)
let mut bit: i32 = 0
let mut tmp: i128 = lsb
while tmp > (1 as i128) {
tmp = tmp >> (1 as i128)
bit = bit + 1
}
pos_out[cnt] = (k as i64) * t + (bit as i64)
cnt = cnt + 1
x = x - lsb
}
if k < r {
c = c * ((r - k) as i128) / ((k + 1) as i128)
}
k = k + 1
}
return cnt
}
function powmod(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut r: i64 = 1 % mod
let mut b: i64 = base0 % mod
if b < 0 {
b = b + mod
}
let mut e: i64 = exp0
while e > 0 {
if (e & 1) == 1 {
r = (((r as i128) * (b as i128)) % (mod as i128)) as i64
}
b = (((b as i128) * (b as i128)) % (mod as i128)) as i64
e = e >> 1
}
return r
}
# Compute A(n) given positions of 1-bits in n (sorted increasing), mod MOD
function A_from_positions(pos: ptr<i64>, m: i32, mod: i64) -> i64 {
if m == 0 {
return 0
}
if m == 1 {
return 1 % mod
}
let v: ptr<i64> = calloc((m as i64), 8)
v[0] = 1 % mod
let mut k: i32 = 1
while k < m {
v[k] = (5 * v[k - 1] + 3) % mod
k = k + 1
}
let mut ans: i64 = 1 % mod
let mut i: i32 = 0
while i < m - 1 {
let gap: i64 = pos[(m - 1 - i) as i64] - pos[(m - 1 - i - 1) as i64] - 1
if gap <= 0 {
i = i + 1
continue
}
let base: i64 = v[(i + 1) as i64]
ans = (ans * powmod(base, gap, mod)) % mod
i = i + 1
}
free(v)
return ans
}
function main() -> i32 {
let t: i64 = 100000000000031
let r: i32 = 62
let maxbits: i32 = 4000
let pos: ptr<i64> = calloc((maxbits as i64), 8)
let npos: i32 = one_positions_via_binom(t, r, pos)
let result: i64 = A_from_positions(pos, npos, MOD)
free(pos)
printf("%lld\n", result)
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; }
int32_t one_positions_via_binom_i64_i32_ptr_i64(int64_t t, int32_t r, int64_t* pos_out);
int64_t powmod_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int64_t A_from_positions_ptr_i64_i32_i64(int64_t* pos, int32_t m, int64_t mod);
int32_t main(void);
static const int64_t MOD = 1000062031;
int32_t one_positions_via_binom_i64_i32_ptr_i64(int64_t t, int32_t r, int64_t* pos_out) {
int32_t cnt = 0;
__int128 c = ((__int128)(1));
int32_t k = 0;
while (k <= r) {
__int128 x = c;
while (x != ((__int128)(0))) {
__int128 lsb = (x & (((__int128)(0)) - x));
int32_t bit = 0;
__int128 tmp = lsb;
while (tmp > ((__int128)(1))) {
tmp = FLOW_CHECKED_SHR((tmp), (((__int128)(1))));
bit = (bit + 1);
}
pos_out[cnt] = ((((int64_t)(k)) * t) + ((int64_t)(bit)));
cnt = (cnt + 1);
x = (x - lsb);
}
if (k < r) {
c = FLOW_CHECKED_DIV(((c * ((__int128)((r - k))))), (((__int128)((k + 1)))));
}
k = (k + 1);
}
return cnt;
}
int64_t powmod_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t r = FLOW_CHECKED_MOD((1), (mod));
int64_t b = FLOW_CHECKED_MOD((base0), (mod));
if (b < 0) {
b = (b + mod);
}
int64_t e = exp0;
while (e > 0) {
if ((e & 1) == 1) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(b)))), (((__int128)(mod))))));
}
b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(mod))))));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t A_from_positions_ptr_i64_i32_i64(int64_t* pos, int32_t m, int64_t mod) {
if (m == 0) {
return 0;
}
if (m == 1) {
return FLOW_CHECKED_MOD((1), (mod));
}
int64_t* v = (int64_t*)(calloc(((int64_t)(m)), 8));
v[0] = FLOW_CHECKED_MOD((1), (mod));
int32_t k = 1;
while (k < m) {
v[k] = FLOW_CHECKED_MOD((((5 * v[(k - 1)]) + 3)), (mod));
k = (k + 1);
}
int64_t ans = FLOW_CHECKED_MOD((1), (mod));
int32_t i = 0;
while (i < (m - 1)) {
int64_t gap = ((pos[((int64_t)(((m - 1) - i)))] - pos[((int64_t)((((m - 1) - i) - 1)))]) - 1);
if (gap <= 0) {
i = (i + 1);
continue;
}
int64_t base = v[((int64_t)((i + 1)))];
ans = FLOW_CHECKED_MOD(((ans * powmod_i64_i64_i64(base, gap, mod))), (mod));
i = (i + 1);
}
free(v);
return ans;
}
int32_t main(void) {
int64_t t = 100000000000031;
int32_t r = 62;
int32_t maxbits = 4000;
int64_t* pos = (int64_t*)(calloc(((int64_t)(maxbits)), 8));
int32_t npos = one_positions_via_binom_i64_i32_ptr_i64(t, r, pos);
int64_t result = A_from_positions_ptr_i64_i32_i64(pos, npos, MOD);
free(pos);
printf("%lld\n", result);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000062031 : i64) : i64
func.func @one_positions_via_binom(%arg0: i64, %arg1: i32, %arg2: !llvm.ptr) -> i32 {
%0 = arith.constant 0 : i32
%1 = llvm.mlir.constant(1 : i64) : i64
%2 = llvm.alloca %1 x i32 : (i64) -> !llvm.ptr
llvm.store %0, %2 : i32, !llvm.ptr
%3 = arith.constant 1 : i32
%4 = arith.extsi %3 : i32 to i128
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i128 : (i64) -> !llvm.ptr
llvm.store %4, %6 : i128, !llvm.ptr
%7 = arith.constant 0 : i32
%8 = llvm.mlir.constant(1 : i64) : i64
%9 = llvm.alloca %8 x i32 : (i64) -> !llvm.ptr
llvm.store %7, %9 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%10 = llvm.load %9 : !llvm.ptr -> i32
%11 = arith.cmpi sle, %10, %arg1 : i32
cf.cond_br %11, ^bb1, ^bb2
^bb1:
%12 = llvm.load %6 : !llvm.ptr -> i128
%13 = llvm.mlir.constant(1 : i64) : i64
%14 = llvm.alloca %13 x i128 : (i64) -> !llvm.ptr
llvm.store %12, %14 : i128, !llvm.ptr
cf.br ^bb3
^bb3:
%15 = llvm.load %14 : !llvm.ptr -> i128
%16 = arith.constant 0 : i32
%17 = arith.extsi %16 : i32 to i128
%19 = arith.trunci %15 : i128 to i64
%20 = arith.trunci %17 : i128 to i64
%18 = arith.cmpi ne, %19, %20 : i64
cf.cond_br %18, ^bb4, ^bb5
^bb4:
%21 = llvm.load %14 : !llvm.ptr -> i128
%22 = arith.constant 0 : i32
%23 = arith.extsi %22 : i32 to i128
%24 = llvm.load %14 : !llvm.ptr -> i128
%26 = arith.trunci %23 : i128 to i64
%27 = arith.trunci %24 : i128 to i64
%25 = arith.subi %26, %27 : i64
%29 = arith.trunci %21 : i128 to i64
%28 = arith.andi %29, %25 : i64
%30 = arith.extsi %28 : i64 to i128
%31 = arith.constant 0 : i32
%32 = llvm.mlir.constant(1 : i64) : i64
%33 = llvm.alloca %32 x i32 : (i64) -> !llvm.ptr
llvm.store %31, %33 : i32, !llvm.ptr
%34 = llvm.mlir.constant(1 : i64) : i64
%35 = llvm.alloca %34 x i128 : (i64) -> !llvm.ptr
llvm.store %30, %35 : i128, !llvm.ptr
cf.br ^bb6
^bb6:
%36 = llvm.load %35 : !llvm.ptr -> i128
%37 = arith.constant 1 : i32
%38 = arith.extsi %37 : i32 to i128
%40 = arith.trunci %36 : i128 to i64
%41 = arith.trunci %38 : i128 to i64
%39 = arith.cmpi sgt, %40, %41 : i64
cf.cond_br %39, ^bb7, ^bb8
^bb7:
%42 = llvm.load %35 : !llvm.ptr -> i128
%43 = arith.constant 1 : i32
%44 = arith.extsi %43 : i32 to i128
%46 = arith.trunci %42 : i128 to i64
%47 = arith.trunci %44 : i128 to i64
%45 = arith.shrsi %46, %47 : i64
%48 = arith.extsi %45 : i64 to i128
llvm.store %48, %35 : i128, !llvm.ptr
%49 = llvm.load %33 : !llvm.ptr -> i32
%50 = arith.constant 1 : i32
%51 = arith.addi %49, %50 : i32
llvm.store %51, %33 : i32, !llvm.ptr
cf.br ^bb6
^bb8:
%52 = llvm.load %9 : !llvm.ptr -> i32
%53 = arith.extsi %52 : i32 to i64
%54 = arith.muli %53, %arg0 : i64
%55 = llvm.load %33 : !llvm.ptr -> i32
%56 = arith.extsi %55 : i32 to i64
%57 = arith.addi %54, %56 : i64
%58 = llvm.load %2 : !llvm.ptr -> i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.getelementptr %arg2[%59] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %57, %60 : i64, !llvm.ptr
%61 = llvm.load %2 : !llvm.ptr -> i32
%62 = arith.constant 1 : i32
%63 = arith.addi %61, %62 : i32
llvm.store %63, %2 : i32, !llvm.ptr
%64 = llvm.load %14 : !llvm.ptr -> i128
%66 = arith.trunci %64 : i128 to i64
%67 = arith.trunci %30 : i128 to i64
%65 = arith.subi %66, %67 : i64
%68 = arith.extsi %65 : i64 to i128
llvm.store %68, %14 : i128, !llvm.ptr
cf.br ^bb3
^bb5:
%69 = llvm.load %9 : !llvm.ptr -> i32
%70 = arith.cmpi slt, %69, %arg1 : i32
cf.cond_br %70, ^bb9, ^bb10
^bb9:
%71 = llvm.load %6 : !llvm.ptr -> i128
%72 = llvm.load %9 : !llvm.ptr -> i32
%73 = arith.subi %arg1, %72 : i32
%74 = arith.extsi %73 : i32 to i128
%76 = arith.trunci %71 : i128 to i64
%77 = arith.trunci %74 : i128 to i64
%75 = arith.muli %76, %77 : i64
%78 = llvm.load %9 : !llvm.ptr -> i32
%79 = arith.constant 1 : i32
%80 = arith.addi %78, %79 : i32
%81 = arith.extsi %80 : i32 to i128
%83 = arith.trunci %81 : i128 to i64
%82 = arith.divsi %75, %83 : i64
%84 = arith.extsi %82 : i64 to i128
llvm.store %84, %6 : i128, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%85 = llvm.load %9 : !llvm.ptr -> i32
%86 = arith.constant 1 : i32
%87 = arith.addi %85, %86 : i32
llvm.store %87, %9 : i32, !llvm.ptr
cf.br ^bb0
^bb2:
%88 = llvm.load %2 : !llvm.ptr -> i32
func.return %88 : i32
}
func.func @powmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%89 = arith.constant 1 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.remsi %91, %arg2 : i64
%92 = llvm.mlir.constant(1 : i64) : i64
%93 = llvm.alloca %92 x i64 : (i64) -> !llvm.ptr
llvm.store %90, %93 : i64, !llvm.ptr
%94 = arith.remsi %arg0, %arg2 : i64
%95 = llvm.mlir.constant(1 : i64) : i64
%96 = llvm.alloca %95 x i64 : (i64) -> !llvm.ptr
llvm.store %94, %96 : i64, !llvm.ptr
%97 = llvm.load %96 : !llvm.ptr -> i64
%98 = arith.constant 0 : i32
%100 = arith.extsi %98 : i32 to i64
%99 = arith.cmpi slt, %97, %100 : i64
cf.cond_br %99, ^bb12, ^bb13
^bb12:
%101 = llvm.load %96 : !llvm.ptr -> i64
%102 = arith.addi %101, %arg2 : i64
llvm.store %102, %96 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%103 = llvm.mlir.constant(1 : i64) : i64
%104 = llvm.alloca %103 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %104 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%105 = llvm.load %104 : !llvm.ptr -> i64
%106 = arith.constant 0 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.cmpi sgt, %105, %108 : i64
cf.cond_br %107, ^bb16, ^bb17
^bb16:
%109 = llvm.load %104 : !llvm.ptr -> i64
%110 = arith.constant 1 : i32
%112 = arith.extsi %110 : i32 to i64
%111 = arith.andi %109, %112 : i64
%113 = arith.constant 1 : i32
%115 = arith.extsi %113 : i32 to i64
%114 = arith.cmpi eq, %111, %115 : i64
cf.cond_br %114, ^bb18, ^bb19
^bb18:
%116 = llvm.load %93 : !llvm.ptr -> i64
%117 = arith.extsi %116 : i64 to i128
%118 = llvm.load %96 : !llvm.ptr -> i64
%119 = arith.extsi %118 : i64 to i128
%121 = arith.trunci %117 : i128 to i64
%122 = arith.trunci %119 : i128 to i64
%120 = arith.muli %121, %122 : i64
%123 = arith.extsi %arg2 : i64 to i128
%125 = arith.trunci %123 : i128 to i64
%124 = arith.remsi %120, %125 : i64
llvm.store %124, %93 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%126 = llvm.load %96 : !llvm.ptr -> i64
%127 = arith.extsi %126 : i64 to i128
%128 = llvm.load %96 : !llvm.ptr -> i64
%129 = arith.extsi %128 : i64 to i128
%131 = arith.trunci %127 : i128 to i64
%132 = arith.trunci %129 : i128 to i64
%130 = arith.muli %131, %132 : i64
%133 = arith.extsi %arg2 : i64 to i128
%135 = arith.trunci %133 : i128 to i64
%134 = arith.remsi %130, %135 : i64
llvm.store %134, %96 : i64, !llvm.ptr
%136 = llvm.load %104 : !llvm.ptr -> i64
%137 = arith.constant 1 : i32
%139 = arith.extsi %137 : i32 to i64
%138 = arith.shrsi %136, %139 : i64
llvm.store %138, %104 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%140 = llvm.load %93 : !llvm.ptr -> i64
func.return %140 : i64
}
func.func @A_from_positions(%arg0: !llvm.ptr, %arg1: i32, %arg2: i64) -> i64 {
%141 = arith.constant 0 : i32
%142 = arith.cmpi eq, %arg1, %141 : i32
cf.cond_br %142, ^bb21, ^bb22
^bb21:
%143 = arith.constant 0 : i32
%144 = arith.extsi %143 : i32 to i64
func.return %144 : i64
^bb22:
cf.br ^bb23
^bb23:
%145 = arith.constant 1 : i32
%146 = arith.cmpi eq, %arg1, %145 : i32
cf.cond_br %146, ^bb24, ^bb25
^bb24:
%147 = arith.constant 1 : i32
%149 = arith.extsi %147 : i32 to i64
%148 = arith.remsi %149, %arg2 : i64
func.return %148 : i64
^bb25:
cf.br ^bb26
^bb26:
%151 = arith.extsi %arg1 : i32 to i64
%152 = arith.constant 8 : i32
%153 = arith.extsi %152 : i32 to i64
%150 = func.call @calloc(%151, %153) : (i64, i64) -> !llvm.ptr
%154 = arith.constant 1 : i32
%156 = arith.extsi %154 : i32 to i64
%155 = arith.remsi %156, %arg2 : i64
%157 = arith.constant 0 : i32
%158 = arith.extsi %157 : i32 to i64
%159 = llvm.getelementptr %150[%158] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %155, %159 : i64, !llvm.ptr
%160 = arith.constant 1 : i32
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i32 : (i64) -> !llvm.ptr
llvm.store %160, %162 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%163 = llvm.load %162 : !llvm.ptr -> i32
%164 = arith.cmpi slt, %163, %arg1 : i32
cf.cond_br %164, ^bb28, ^bb29
^bb28:
%165 = arith.constant 5 : i32
%167 = llvm.load %162 : !llvm.ptr -> i32
%168 = arith.constant 1 : i32
%169 = arith.subi %167, %168 : i32
%170 = arith.extsi %169 : i32 to i64
%171 = llvm.getelementptr %150[%170] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%166 = llvm.load %171 : !llvm.ptr -> i64
%173 = arith.extsi %165 : i32 to i64
%172 = arith.muli %173, %166 : i64
%174 = arith.constant 3 : i32
%176 = arith.extsi %174 : i32 to i64
%175 = arith.addi %172, %176 : i64
%177 = arith.remsi %175, %arg2 : i64
%178 = llvm.load %162 : !llvm.ptr -> i32
%179 = arith.extsi %178 : i32 to i64
%180 = llvm.getelementptr %150[%179] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %177, %180 : i64, !llvm.ptr
%181 = llvm.load %162 : !llvm.ptr -> i32
%182 = arith.constant 1 : i32
%183 = arith.addi %181, %182 : i32
llvm.store %183, %162 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%184 = arith.constant 1 : i32
%186 = arith.extsi %184 : i32 to i64
%185 = arith.remsi %186, %arg2 : i64
%187 = llvm.mlir.constant(1 : i64) : i64
%188 = llvm.alloca %187 x i64 : (i64) -> !llvm.ptr
llvm.store %185, %188 : i64, !llvm.ptr
%189 = arith.constant 0 : i32
%190 = llvm.mlir.constant(1 : i64) : i64
%191 = llvm.alloca %190 x i32 : (i64) -> !llvm.ptr
llvm.store %189, %191 : i32, !llvm.ptr
cf.br ^bb30
^bb30:
%192 = llvm.load %191 : !llvm.ptr -> i32
%193 = arith.constant 1 : i32
%194 = arith.subi %arg1, %193 : i32
%195 = arith.cmpi slt, %192, %194 : i32
cf.cond_br %195, ^bb31, ^bb32
^bb31:
%197 = arith.constant 1 : i32
%198 = arith.subi %arg1, %197 : i32
%199 = llvm.load %191 : !llvm.ptr -> i32
%200 = arith.subi %198, %199 : i32
%201 = arith.extsi %200 : i32 to i64
%202 = llvm.getelementptr %arg0[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%196 = llvm.load %202 : !llvm.ptr -> i64
%204 = arith.constant 1 : i32
%205 = arith.subi %arg1, %204 : i32
%206 = llvm.load %191 : !llvm.ptr -> i32
%207 = arith.subi %205, %206 : i32
%208 = arith.constant 1 : i32
%209 = arith.subi %207, %208 : i32
%210 = arith.extsi %209 : i32 to i64
%211 = llvm.getelementptr %arg0[%210] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%203 = llvm.load %211 : !llvm.ptr -> i64
%212 = arith.subi %196, %203 : i64
%213 = arith.constant 1 : i32
%215 = arith.extsi %213 : i32 to i64
%214 = arith.subi %212, %215 : i64
%216 = arith.constant 0 : i32
%218 = arith.extsi %216 : i32 to i64
%217 = arith.cmpi sle, %214, %218 : i64
cf.cond_br %217, ^bb33, ^bb34
^bb33:
%219 = llvm.load %191 : !llvm.ptr -> i32
%220 = arith.constant 1 : i32
%221 = arith.addi %219, %220 : i32
llvm.store %221, %191 : i32, !llvm.ptr
cf.br ^bb30
^bb34:
cf.br ^bb35
^bb35:
%223 = llvm.load %191 : !llvm.ptr -> i32
%224 = arith.constant 1 : i32
%225 = arith.addi %223, %224 : i32
%226 = arith.extsi %225 : i32 to i64
%227 = llvm.getelementptr %150[%226] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%222 = llvm.load %227 : !llvm.ptr -> i64
%228 = llvm.load %188 : !llvm.ptr -> i64
%229 = func.call @powmod(%222, %214, %arg2) : (i64, i64, i64) -> i64
%230 = arith.muli %228, %229 : i64
%231 = arith.remsi %230, %arg2 : i64
llvm.store %231, %188 : i64, !llvm.ptr
%232 = llvm.load %191 : !llvm.ptr -> i32
%233 = arith.constant 1 : i32
%234 = arith.addi %232, %233 : i32
llvm.store %234, %191 : i32, !llvm.ptr
cf.br ^bb30
^bb32:
func.call @free(%150) : (!llvm.ptr) -> ()
%236 = llvm.load %188 : !llvm.ptr -> i64
func.return %236 : i64
}
func.func @main() -> i32 {
%237 = arith.constant 99995705032735 : i32
%238 = arith.extsi %237 : i32 to i64
%239 = arith.constant 62 : i32
%240 = arith.constant 4000 : i32
%242 = arith.extsi %240 : i32 to i64
%243 = arith.constant 8 : i32
%244 = arith.extsi %243 : i32 to i64
%241 = func.call @calloc(%242, %244) : (i64, i64) -> !llvm.ptr
%245 = func.call @one_positions_via_binom(%238, %239, %241) : (i64, i32, !llvm.ptr) -> i32
%247 = llvm.mlir.addressof @MOD : !llvm.ptr
%248 = llvm.load %247 : !llvm.ptr -> i64
%246 = func.call @A_from_positions(%241, %245, %248) : (!llvm.ptr, i32, i64) -> i64
func.call @free(%241) : (!llvm.ptr) -> ()
%250 = llvm.mlir.addressof @str_0 : !llvm.ptr
%251 = llvm.call @printf(%250, %246) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%252 = arith.constant 0 : i32
func.return %252 : i32
}
}