Problem 1005

Median Prime List: product of primes in the median prime list summing to 2026, mod 1e9. Sieve primes up to N, DP to count subset-sums, reconstruct the median subset, multiply.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 1005
# Median Prime List: product of primes in the median prime list summing to 2026, mod 1e9.
# Sieve primes up to N, DP to count subset-sums, reconstruct the median subset, multiply.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
}

const MOD: i64 = 1000000000

function main() -> i32 {
    let N: i64 = 2026

    # Sieve primes up to N
    let sieve: ptr<i8> = calloc(N + 1, 1)
    sieve[0] = 1
    sieve[1] = 1
    let mut p: i64 = 2
    while p * p <= N {
        if sieve[p] == 0 {
            let mut m: i64 = p * p
            while m <= N {
                sieve[m] = 1
                m = m + p
            }
        }
        p = p + 1
    }

    # Collect primes
    let primes: ptr<i64> = calloc(N + 1, 8)
    let mut np: i64 = 0
    let mut i: i64 = 2
    while i <= N {
        if sieve[i] == 0 {
            primes[np] = i
            np = np + 1
        }
        i = i + 1
    }

    # DP: count[index][sum] = number of ways to form sum using primes[index..np]
    # count[np][0] = 1, count[np][s>0] = 0
    # count[i][s] = count[i+1][s] + (s >= primes[i] ? count[i+1][s - primes[i]] : 0)
    let dp: ptr<i64> = calloc((np + 1) * (N + 1), 8)
    dp[np * (N + 1) + 0] = 1

    let mut idx: i64 = np - 1
    while idx >= 0 {
        let mut s: i64 = 0
        while s <= N {
            dp[idx * (N + 1) + s] = dp[(idx + 1) * (N + 1) + s]
            if s >= primes[idx] {
                dp[idx * (N + 1) + s] = dp[idx * (N + 1) + s] + dp[(idx + 1) * (N + 1) + s - primes[idx]]
            }
            s = s + 1
        }
        idx = idx - 1
    }

    # The median is the (total_ways - 1) / 2-th subset (0-indexed)
    let total_ways: i64 = dp[0 * (N + 1) + N]
    let mut rank: i64 = (total_ways - 1) / 2

    # Reconstruct the median prime list
    let mut product: i64 = 1
    let mut remaining: i64 = N
    let mut start: i64 = 0

    while remaining > 0 {
        let mut j: i64 = start
        while j < np {
            if primes[j] > remaining {
                break
            }
            let block: i64 = dp[(j + 1) * (N + 1) + remaining - primes[j]]
            if rank >= block {
                rank = rank - block
            } else {
                product = product * primes[j] % MOD
                remaining = remaining - primes[j]
                start = j + 1
                break
            }
            j = j + 1
        }
    }

    printf("%lld\n", product)

    free(sieve)
    free(primes)
    free(dp)
    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 main(void);

static const int64_t MOD = 1000000000;



int32_t main(void) {
    int64_t N = 2026;
    int8_t* sieve = (int8_t*)(calloc((N + 1), 1));
    sieve[0] = 1;
    sieve[1] = 1;
    int64_t p = 2;
    while ((p * p) <= N) {
        if (sieve[p] == 0) {
            int64_t m = (p * p);
            while (m <= N) {
                sieve[m] = 1;
                m = (m + p);
            }
        }
        p = (p + 1);
    }
    int64_t* primes = (int64_t*)(calloc((N + 1), 8));
    int64_t np = 0;
    int64_t i = 2;
    while (i <= N) {
        if (sieve[i] == 0) {
            primes[np] = i;
            np = (np + 1);
        }
        i = (i + 1);
    }
    int64_t* dp = (int64_t*)(calloc(((np + 1) * (N + 1)), 8));
    dp[((np * (N + 1)) + 0)] = 1;
    int64_t idx = (np - 1);
    while (idx >= 0) {
        int64_t s = 0;
        while (s <= N) {
            dp[((idx * (N + 1)) + s)] = dp[(((idx + 1) * (N + 1)) + s)];
            if (s >= primes[idx]) {
                dp[((idx * (N + 1)) + s)] = (dp[((idx * (N + 1)) + s)] + dp[((((idx + 1) * (N + 1)) + s) - primes[idx])]);
            }
            s = (s + 1);
        }
        idx = (idx - 1);
    }
    int64_t total_ways = dp[((0 * (N + 1)) + N)];
    int64_t rank = FLOW_CHECKED_DIV(((total_ways - 1)), (2));
    int64_t product = 1;
    int64_t remaining = N;
    int64_t start = 0;
    while (remaining > 0) {
        int64_t j = start;
        while (j < np) {
            if (primes[j] > remaining) {
                break;
            }
            int64_t block = dp[((((j + 1) * (N + 1)) + remaining) - primes[j])];
            if (rank >= block) {
                rank = (rank - block);
            } else {
                product = FLOW_CHECKED_MOD(((product * primes[j])), (MOD));
                remaining = (remaining - primes[j]);
                start = (j + 1);
                break;
            }
            j = (j + 1);
        }
    }
    printf("%lld\n", product);
    free(sieve);
    free(primes);
    free(dp);
    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(1000000000 : i64) : i64
  func.func @main() -> i32 {
    %0 = arith.constant 2026 : i32
    %1 = arith.extsi %0 : i32 to i64
    %3 = arith.constant 1 : i32
    %5 = arith.extsi %3 : i32 to i64
    %4 = arith.addi %1, %5 : i64
    %6 = arith.constant 1 : i32
    %7 = arith.extsi %6 : i32 to i64
    %2 = func.call @calloc(%4, %7) : (i64, i64) -> !llvm.ptr
    %8 = arith.constant 1 : i32
    %9 = arith.constant 0 : i32
    %10 = arith.trunci %8 : i32 to i8
    %11 = arith.extsi %9 : i32 to i64
    %12 = llvm.getelementptr %2[%11] : (!llvm.ptr, i64) -> !llvm.ptr, i8
    llvm.store %10, %12 : i8, !llvm.ptr
    %13 = arith.constant 1 : i32
    %14 = arith.constant 1 : i32
    %15 = arith.trunci %13 : i32 to i8
    %16 = arith.extsi %14 : i32 to i64
    %17 = llvm.getelementptr %2[%16] : (!llvm.ptr, i64) -> !llvm.ptr, i8
    llvm.store %15, %17 : i8, !llvm.ptr
    %18 = arith.constant 2 : i32
    %19 = arith.extsi %18 : i32 to i64
    %20 = llvm.mlir.constant(1 : i64) : i64
    %21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
    llvm.store %19, %21 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %22 = llvm.load %21 : !llvm.ptr -> i64
    %23 = llvm.load %21 : !llvm.ptr -> i64
    %24 = arith.muli %22, %23 : i64
    %25 = arith.cmpi sle, %24, %1 : i64
    cf.cond_br %25, ^bb1, ^bb2
    ^bb1:
      %27 = llvm.load %21 : !llvm.ptr -> i64
      %28 = llvm.getelementptr %2[%27] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      %26 = llvm.load %28 : !llvm.ptr -> i8
      %29 = arith.constant 0 : i32
      %31 = arith.extsi %26 : i8 to i32
      %30 = arith.cmpi eq, %31, %29 : i32
      cf.cond_br %30, ^bb3, ^bb4
      ^bb3:
        %32 = llvm.load %21 : !llvm.ptr -> i64
        %33 = llvm.load %21 : !llvm.ptr -> i64
        %34 = arith.muli %32, %33 : i64
        %35 = llvm.mlir.constant(1 : i64) : i64
        %36 = llvm.alloca %35 x i64 : (i64) -> !llvm.ptr
        llvm.store %34, %36 : i64, !llvm.ptr
        cf.br ^bb6
        ^bb6:
        %37 = llvm.load %36 : !llvm.ptr -> i64
        %38 = arith.cmpi sle, %37, %1 : i64
        cf.cond_br %38, ^bb7, ^bb8
        ^bb7:
          %39 = arith.constant 1 : i32
          %40 = llvm.load %36 : !llvm.ptr -> i64
          %41 = arith.trunci %39 : i32 to i8
          %42 = llvm.getelementptr %2[%40] : (!llvm.ptr, i64) -> !llvm.ptr, i8
          llvm.store %41, %42 : i8, !llvm.ptr
          %43 = llvm.load %36 : !llvm.ptr -> i64
          %44 = llvm.load %21 : !llvm.ptr -> i64
          %45 = arith.addi %43, %44 : i64
          llvm.store %45, %36 : i64, !llvm.ptr
          cf.br ^bb6
        ^bb8:
        cf.br ^bb5
      ^bb4:
        cf.br ^bb5
      ^bb5:
      %46 = llvm.load %21 : !llvm.ptr -> i64
      %47 = arith.constant 1 : i32
      %49 = arith.extsi %47 : i32 to i64
      %48 = arith.addi %46, %49 : i64
      llvm.store %48, %21 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %51 = arith.constant 1 : i32
    %53 = arith.extsi %51 : i32 to i64
    %52 = arith.addi %1, %53 : i64
    %54 = arith.constant 8 : i32
    %55 = arith.extsi %54 : i32 to i64
    %50 = func.call @calloc(%52, %55) : (i64, i64) -> !llvm.ptr
    %56 = arith.constant 0 : i32
    %57 = arith.extsi %56 : i32 to i64
    %58 = llvm.mlir.constant(1 : i64) : i64
    %59 = llvm.alloca %58 x i64 : (i64) -> !llvm.ptr
    llvm.store %57, %59 : i64, !llvm.ptr
    %60 = arith.constant 2 : i32
    %61 = arith.extsi %60 : i32 to i64
    %62 = llvm.mlir.constant(1 : i64) : i64
    %63 = llvm.alloca %62 x i64 : (i64) -> !llvm.ptr
    llvm.store %61, %63 : i64, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %64 = llvm.load %63 : !llvm.ptr -> i64
    %65 = arith.cmpi sle, %64, %1 : i64
    cf.cond_br %65, ^bb10, ^bb11
    ^bb10:
      %67 = llvm.load %63 : !llvm.ptr -> i64
      %68 = llvm.getelementptr %2[%67] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      %66 = llvm.load %68 : !llvm.ptr -> i8
      %69 = arith.constant 0 : i32
      %71 = arith.extsi %66 : i8 to i32
      %70 = arith.cmpi eq, %71, %69 : i32
      cf.cond_br %70, ^bb12, ^bb13
      ^bb12:
        %72 = llvm.load %63 : !llvm.ptr -> i64
        %73 = llvm.load %59 : !llvm.ptr -> i64
        %74 = llvm.getelementptr %50[%73] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %72, %74 : i64, !llvm.ptr
        %75 = llvm.load %59 : !llvm.ptr -> i64
        %76 = arith.constant 1 : i32
        %78 = arith.extsi %76 : i32 to i64
        %77 = arith.addi %75, %78 : i64
        llvm.store %77, %59 : i64, !llvm.ptr
        cf.br ^bb14
      ^bb13:
        cf.br ^bb14
      ^bb14:
      %79 = llvm.load %63 : !llvm.ptr -> i64
      %80 = arith.constant 1 : i32
      %82 = arith.extsi %80 : i32 to i64
      %81 = arith.addi %79, %82 : i64
      llvm.store %81, %63 : i64, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %84 = llvm.load %59 : !llvm.ptr -> i64
    %85 = arith.constant 1 : i32
    %87 = arith.extsi %85 : i32 to i64
    %86 = arith.addi %84, %87 : i64
    %88 = arith.constant 1 : i32
    %90 = arith.extsi %88 : i32 to i64
    %89 = arith.addi %1, %90 : i64
    %91 = arith.muli %86, %89 : i64
    %92 = arith.constant 8 : i32
    %93 = arith.extsi %92 : i32 to i64
    %83 = func.call @calloc(%91, %93) : (i64, i64) -> !llvm.ptr
    %94 = arith.constant 1 : i32
    %95 = llvm.load %59 : !llvm.ptr -> i64
    %96 = arith.constant 1 : i32
    %98 = arith.extsi %96 : i32 to i64
    %97 = arith.addi %1, %98 : i64
    %99 = arith.muli %95, %97 : i64
    %100 = arith.constant 0 : i32
    %102 = arith.extsi %100 : i32 to i64
    %101 = arith.addi %99, %102 : i64
    %103 = arith.extsi %94 : i32 to i64
    %104 = llvm.getelementptr %83[%101] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %103, %104 : i64, !llvm.ptr
    %105 = llvm.load %59 : !llvm.ptr -> i64
    %106 = arith.constant 1 : i32
    %108 = arith.extsi %106 : i32 to i64
    %107 = arith.subi %105, %108 : i64
    %109 = llvm.mlir.constant(1 : i64) : i64
    %110 = llvm.alloca %109 x i64 : (i64) -> !llvm.ptr
    llvm.store %107, %110 : i64, !llvm.ptr
    cf.br ^bb15
    ^bb15:
    %111 = llvm.load %110 : !llvm.ptr -> i64
    %112 = arith.constant 0 : i32
    %114 = arith.extsi %112 : i32 to i64
    %113 = arith.cmpi sge, %111, %114 : i64
    cf.cond_br %113, ^bb16, ^bb17
    ^bb16:
      %115 = arith.constant 0 : i32
      %116 = arith.extsi %115 : i32 to i64
      %117 = llvm.mlir.constant(1 : i64) : i64
      %118 = llvm.alloca %117 x i64 : (i64) -> !llvm.ptr
      llvm.store %116, %118 : i64, !llvm.ptr
      cf.br ^bb18
      ^bb18:
      %119 = llvm.load %118 : !llvm.ptr -> i64
      %120 = arith.cmpi sle, %119, %1 : i64
      cf.cond_br %120, ^bb19, ^bb20
      ^bb19:
        %122 = llvm.load %110 : !llvm.ptr -> i64
        %123 = arith.constant 1 : i32
        %125 = arith.extsi %123 : i32 to i64
        %124 = arith.addi %122, %125 : i64
        %126 = arith.constant 1 : i32
        %128 = arith.extsi %126 : i32 to i64
        %127 = arith.addi %1, %128 : i64
        %129 = arith.muli %124, %127 : i64
        %130 = llvm.load %118 : !llvm.ptr -> i64
        %131 = arith.addi %129, %130 : i64
        %132 = llvm.getelementptr %83[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %121 = llvm.load %132 : !llvm.ptr -> i64
        %133 = llvm.load %110 : !llvm.ptr -> i64
        %134 = arith.constant 1 : i32
        %136 = arith.extsi %134 : i32 to i64
        %135 = arith.addi %1, %136 : i64
        %137 = arith.muli %133, %135 : i64
        %138 = llvm.load %118 : !llvm.ptr -> i64
        %139 = arith.addi %137, %138 : i64
        %140 = llvm.getelementptr %83[%139] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %121, %140 : i64, !llvm.ptr
        %141 = llvm.load %118 : !llvm.ptr -> i64
        %143 = llvm.load %110 : !llvm.ptr -> i64
        %144 = llvm.getelementptr %50[%143] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %142 = llvm.load %144 : !llvm.ptr -> i64
        %145 = arith.cmpi sge, %141, %142 : i64
        cf.cond_br %145, ^bb21, ^bb22
        ^bb21:
          %147 = llvm.load %110 : !llvm.ptr -> i64
          %148 = arith.constant 1 : i32
          %150 = arith.extsi %148 : i32 to i64
          %149 = arith.addi %1, %150 : i64
          %151 = arith.muli %147, %149 : i64
          %152 = llvm.load %118 : !llvm.ptr -> i64
          %153 = arith.addi %151, %152 : i64
          %154 = llvm.getelementptr %83[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %146 = llvm.load %154 : !llvm.ptr -> i64
          %156 = llvm.load %110 : !llvm.ptr -> i64
          %157 = arith.constant 1 : i32
          %159 = arith.extsi %157 : i32 to i64
          %158 = arith.addi %156, %159 : i64
          %160 = arith.constant 1 : i32
          %162 = arith.extsi %160 : i32 to i64
          %161 = arith.addi %1, %162 : i64
          %163 = arith.muli %158, %161 : i64
          %164 = llvm.load %118 : !llvm.ptr -> i64
          %165 = arith.addi %163, %164 : i64
          %167 = llvm.load %110 : !llvm.ptr -> i64
          %168 = llvm.getelementptr %50[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %166 = llvm.load %168 : !llvm.ptr -> i64
          %169 = arith.subi %165, %166 : i64
          %170 = llvm.getelementptr %83[%169] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %155 = llvm.load %170 : !llvm.ptr -> i64
          %171 = arith.addi %146, %155 : i64
          %172 = llvm.load %110 : !llvm.ptr -> i64
          %173 = arith.constant 1 : i32
          %175 = arith.extsi %173 : i32 to i64
          %174 = arith.addi %1, %175 : i64
          %176 = arith.muli %172, %174 : i64
          %177 = llvm.load %118 : !llvm.ptr -> i64
          %178 = arith.addi %176, %177 : i64
          %179 = llvm.getelementptr %83[%178] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %171, %179 : i64, !llvm.ptr
          cf.br ^bb23
        ^bb22:
          cf.br ^bb23
        ^bb23:
        %180 = llvm.load %118 : !llvm.ptr -> i64
        %181 = arith.constant 1 : i32
        %183 = arith.extsi %181 : i32 to i64
        %182 = arith.addi %180, %183 : i64
        llvm.store %182, %118 : i64, !llvm.ptr
        cf.br ^bb18
      ^bb20:
      %184 = llvm.load %110 : !llvm.ptr -> i64
      %185 = arith.constant 1 : i32
      %187 = arith.extsi %185 : i32 to i64
      %186 = arith.subi %184, %187 : i64
      llvm.store %186, %110 : i64, !llvm.ptr
      cf.br ^bb15
    ^bb17:
    %189 = arith.constant 0 : i32
    %190 = arith.constant 1 : i32
    %192 = arith.extsi %190 : i32 to i64
    %191 = arith.addi %1, %192 : i64
    %194 = arith.extsi %189 : i32 to i64
    %193 = arith.muli %194, %191 : i64
    %195 = arith.addi %193, %1 : i64
    %196 = llvm.getelementptr %83[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    %188 = llvm.load %196 : !llvm.ptr -> i64
    %197 = arith.constant 1 : i32
    %199 = arith.extsi %197 : i32 to i64
    %198 = arith.subi %188, %199 : i64
    %200 = arith.constant 2 : i32
    %202 = arith.extsi %200 : i32 to i64
    %201 = arith.divsi %198, %202 : i64
    %203 = llvm.mlir.constant(1 : i64) : i64
    %204 = llvm.alloca %203 x i64 : (i64) -> !llvm.ptr
    llvm.store %201, %204 : i64, !llvm.ptr
    %205 = arith.constant 1 : i32
    %206 = arith.extsi %205 : i32 to i64
    %207 = llvm.mlir.constant(1 : i64) : i64
    %208 = llvm.alloca %207 x i64 : (i64) -> !llvm.ptr
    llvm.store %206, %208 : i64, !llvm.ptr
    %209 = llvm.mlir.constant(1 : i64) : i64
    %210 = llvm.alloca %209 x i64 : (i64) -> !llvm.ptr
    llvm.store %1, %210 : i64, !llvm.ptr
    %211 = arith.constant 0 : i32
    %212 = arith.extsi %211 : i32 to i64
    %213 = llvm.mlir.constant(1 : i64) : i64
    %214 = llvm.alloca %213 x i64 : (i64) -> !llvm.ptr
    llvm.store %212, %214 : i64, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %215 = llvm.load %210 : !llvm.ptr -> i64
    %216 = arith.constant 0 : i32
    %218 = arith.extsi %216 : i32 to i64
    %217 = arith.cmpi sgt, %215, %218 : i64
    cf.cond_br %217, ^bb25, ^bb26
    ^bb25:
      %219 = llvm.load %214 : !llvm.ptr -> i64
      %220 = llvm.mlir.constant(1 : i64) : i64
      %221 = llvm.alloca %220 x i64 : (i64) -> !llvm.ptr
      llvm.store %219, %221 : i64, !llvm.ptr
      cf.br ^bb27
      ^bb27:
      %222 = llvm.load %221 : !llvm.ptr -> i64
      %223 = llvm.load %59 : !llvm.ptr -> i64
      %224 = arith.cmpi slt, %222, %223 : i64
      cf.cond_br %224, ^bb28, ^bb29
      ^bb28:
        %226 = llvm.load %221 : !llvm.ptr -> i64
        %227 = llvm.getelementptr %50[%226] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %225 = llvm.load %227 : !llvm.ptr -> i64
        %228 = llvm.load %210 : !llvm.ptr -> i64
        %229 = arith.cmpi sgt, %225, %228 : i64
        cf.cond_br %229, ^bb30, ^bb31
        ^bb30:
          cf.br ^bb29
        ^bb31:
          cf.br ^bb32
        ^bb32:
        %231 = llvm.load %221 : !llvm.ptr -> i64
        %232 = arith.constant 1 : i32
        %234 = arith.extsi %232 : i32 to i64
        %233 = arith.addi %231, %234 : i64
        %235 = arith.constant 1 : i32
        %237 = arith.extsi %235 : i32 to i64
        %236 = arith.addi %1, %237 : i64
        %238 = arith.muli %233, %236 : i64
        %239 = llvm.load %210 : !llvm.ptr -> i64
        %240 = arith.addi %238, %239 : i64
        %242 = llvm.load %221 : !llvm.ptr -> i64
        %243 = llvm.getelementptr %50[%242] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %241 = llvm.load %243 : !llvm.ptr -> i64
        %244 = arith.subi %240, %241 : i64
        %245 = llvm.getelementptr %83[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %230 = llvm.load %245 : !llvm.ptr -> i64
        %246 = llvm.load %204 : !llvm.ptr -> i64
        %247 = arith.cmpi sge, %246, %230 : i64
        cf.cond_br %247, ^bb33, ^bb34
        ^bb33:
          %248 = llvm.load %204 : !llvm.ptr -> i64
          %249 = arith.subi %248, %230 : i64
          llvm.store %249, %204 : i64, !llvm.ptr
          cf.br ^bb35
        ^bb34:
          %250 = llvm.load %208 : !llvm.ptr -> i64
          %252 = llvm.load %221 : !llvm.ptr -> i64
          %253 = llvm.getelementptr %50[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %251 = llvm.load %253 : !llvm.ptr -> i64
          %254 = arith.muli %250, %251 : i64
          %255 = llvm.mlir.addressof @MOD : !llvm.ptr
          %256 = llvm.load %255 : !llvm.ptr -> i64
          %257 = arith.remsi %254, %256 : i64
          llvm.store %257, %208 : i64, !llvm.ptr
          %258 = llvm.load %210 : !llvm.ptr -> i64
          %260 = llvm.load %221 : !llvm.ptr -> i64
          %261 = llvm.getelementptr %50[%260] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %259 = llvm.load %261 : !llvm.ptr -> i64
          %262 = arith.subi %258, %259 : i64
          llvm.store %262, %210 : i64, !llvm.ptr
          %263 = llvm.load %221 : !llvm.ptr -> i64
          %264 = arith.constant 1 : i32
          %266 = arith.extsi %264 : i32 to i64
          %265 = arith.addi %263, %266 : i64
          llvm.store %265, %214 : i64, !llvm.ptr
          cf.br ^bb29
        ^bb35:
        %267 = llvm.load %221 : !llvm.ptr -> i64
        %268 = arith.constant 1 : i32
        %270 = arith.extsi %268 : i32 to i64
        %269 = arith.addi %267, %270 : i64
        llvm.store %269, %221 : i64, !llvm.ptr
        cf.br ^bb27
      ^bb29:
      cf.br ^bb24
    ^bb26:
    %271 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %272 = llvm.load %208 : !llvm.ptr -> i64
    %273 = llvm.call @printf(%271, %272) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%2) : (!llvm.ptr) -> ()
    func.call @free(%50) : (!llvm.ptr) -> ()
    func.call @free(%83) : (!llvm.ptr) -> ()
    %277 = arith.constant 0 : i32
    func.return %277 : i32
  }
}