# Project Euler 888: Coin Game
# Count losing positions (XOR of Grundy numbers = 0) with m piles, each size [1..N].
# Uses a 16-point +/-1 filter over 4 bits of Grundy values.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function malloc(n: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const N_VAL: i64 = 12491249
const M_VAL: i32 = 1249
const MOD: i64 = 912491249
const PRE: i32 = 322
const PERIOD: i32 = 11060
const SPLIT_LIMIT: i32 = 600
# ---- modular arithmetic with i128 ----
function mulmod(a: i64, b: i64, m: i64) -> i64 {
return ((a as i128 * b as i128) % (m as i128)) as i64
}
function powmod(a0: i64, e0: i64, m: i64) -> i64 {
let mut r: i64 = 1 % m
let mut a: i64 = a0 % m
if a < 0 { a = a + m }
let mut e: i64 = e0
while e > 0 {
if (e & 1) == 1 { r = mulmod(r, a, m) }
a = mulmod(a, a, m)
e = e >> 1
}
return r
}
function inv_mod(a0: i64, modv: i64) -> i64 {
let mut a: i64 = a0 % modv
if a < 0 { a = a + modv }
let mut x0: i64 = 1
let mut x1: i64 = 0
let mut aa: i64 = a
let mut mm: i64 = modv
while mm != 0 {
let q: i64 = aa / mm
let t: i64 = aa - q * mm
aa = mm
mm = t
let t2: i64 = x0 - q * x1
x0 = x1
x1 = t2
}
if aa != 1 { return -1 }
let mut result: i64 = x0 % modv
if result < 0 { result = result + modv }
return result
}
function popcount(x: i32) -> i32 {
let mut n: i32 = 0
let mut v: i32 = x
while v != 0 {
n = n + 1
v = v & (v - 1)
}
return n
}
# ---- strip p from x: return x_without_p, set v via pointer ----
function strip_p(x: i64, p: i64, x_free: ptr<i64>, v: ptr<i32>) -> void {
x_free[0] = x
v[0] = 0
while x_free[0] % p == 0 {
x_free[0] = x_free[0] / p
v[0] = v[0] + 1
}
}
# ---- factor n into prime powers (parallel arrays) ----
function factor_prime_powers(n: i64, out_p: ptr<i64>, out_pe: ptr<i64>) -> i32 {
let mut count: i32 = 0
let mut x: i64 = n
let mut p: i64 = 2
while p * p <= x {
if x % p == 0 {
let mut pe: i64 = 1
while x % p == 0 {
x = x / p
pe = pe * p
}
out_p[count] = p
out_pe[count] = pe
count = count + 1
}
if p == 2 { p = 3 } else { p = p + 2 }
}
if x > 1 {
out_p[count] = x
out_pe[count] = x
count = count + 1
}
return count
}
# ---- compute Grundy numbers g[0..limit] ----
function compute_grundy(g: ptr<i32>, limit: i32, split_limit: i32) -> void {
let mut n: i32 = 1
while n <= limit {
let mut seen: i32 = 0
# REMOVE = {1, 2, 4, 9}
if n >= 1 { seen = seen | (1 << g[n - 1]) }
if n >= 2 { seen = seen | (1 << g[n - 2]) }
if n >= 4 { seen = seen | (1 << g[n - 4]) }
if n >= 9 { seen = seen | (1 << g[n - 9]) }
let mut max_i: i32 = n - 1
if split_limit > 0 && split_limit < n - 1 { max_i = split_limit }
let mut i: i32 = 1
while i <= max_i {
seen = seen | (1 << (g[i] ^ g[n - i]))
i = i + 1
}
let mut mex: i32 = 0
while ((seen >> mex) & 1) == 1 {
mex = mex + 1
}
g[n] = mex
n = n + 1
}
}
# ---- denominator tables (using parallel global arrays) ----
let mut dt_p: ptr<i64> = null
let mut dt_pe: ptr<i64> = null
let mut dt_den_free: ptr<ptr<i64> > = null
let mut dt_den_v: ptr<ptr<i32> > = null
let mut dt_inv_free: ptr<ptr<i64> > = null
function precompute_den_tables(idx: i32, p: i64, pe: i64, m: i32) -> void {
dt_p[idx] = p
dt_pe[idx] = pe
dt_den_free[idx] = malloc(((m + 1) as i64) * 8) as ptr<i64>
dt_den_v[idx] = malloc(((m + 1) as i64) * 4) as ptr<i32>
dt_inv_free[idx] = malloc(((m + 1) as i64) * 8) as ptr<i64>
dt_den_free[idx][0] = 1
dt_inv_free[idx][0] = 1
let mut i: i32 = 1
while i <= m {
let xf_ptr: ptr<i64> = malloc(8) as ptr<i64>
let v_ptr: ptr<i32> = malloc(4) as ptr<i32>
strip_p(i as i64, p, xf_ptr, v_ptr)
dt_den_free[idx][i] = xf_ptr[0]
dt_den_v[idx][i] = v_ptr[0]
dt_inv_free[idx][i] = inv_mod(xf_ptr[0] % pe, pe)
free(xf_ptr as ptr<void>)
free(v_ptr as ptr<void>)
i = i + 1
}
}
# ---- coefficient of x^m in (1-x)^(-a) * (1+x)^(-(N-a)) mod p^e ----
function coeff_term_mod_prime_power(N_val: i64, m: i32, a: i64, idx: i32) -> i64 {
let p: i64 = dt_p[idx]
let pe: i64 = dt_pe[idx]
let A: i64 = a
let B: i64 = N_val - a
let u: ptr<i64> = calloc((m + 1) as i64, 8) as ptr<i64>
let w: ptr<i64> = calloc((m + 1) as i64, 8) as ptr<i64>
u[0] = 1 % pe
if A != 0 {
let mut res: i64 = 1 % pe
let mut exp: i32 = 0
let mut i: i32 = 1
while i <= m {
let num: i64 = A + (i as i64) - 1
let num_free_ptr: ptr<i64> = malloc(8) as ptr<i64>
let v_num_ptr: ptr<i32> = malloc(4) as ptr<i32>
strip_p(num, p, num_free_ptr, v_num_ptr)
exp = exp + v_num_ptr[0]
exp = exp - dt_den_v[idx][i]
res = mulmod(res, num_free_ptr[0] % pe, pe)
res = mulmod(res, dt_inv_free[idx][i], pe)
u[i] = mulmod(res, powmod(p, exp as i64, pe), pe)
free(num_free_ptr as ptr<void>)
free(v_num_ptr as ptr<void>)
i = i + 1
}
}
w[0] = 1 % pe
if B != 0 {
let mut res: i64 = 1 % pe
let mut exp: i32 = 0
let mut i: i32 = 1
while i <= m {
let num: i64 = B + (i as i64) - 1
let num_free_ptr: ptr<i64> = malloc(8) as ptr<i64>
let v_num_ptr: ptr<i32> = malloc(4) as ptr<i32>
strip_p(num, p, num_free_ptr, v_num_ptr)
exp = exp + v_num_ptr[0]
exp = exp - dt_den_v[idx][i]
res = mulmod(res, num_free_ptr[0] % pe, pe)
res = mulmod(res, dt_inv_free[idx][i], pe)
let mut val: i64 = mulmod(res, powmod(p, exp as i64, pe), pe)
if (i & 1) == 1 { val = (pe - val) % pe }
w[i] = val
free(num_free_ptr as ptr<void>)
free(v_num_ptr as ptr<void>)
i = i + 1
}
}
let mut out: i64 = 0
let mut i: i32 = 0
while i <= m {
out = (out + mulmod(u[i], w[m - i], pe)) % pe
i = i + 1
}
free(u as ptr<void>)
free(w as ptr<void>)
return out
}
# ---- count Grundy values in [1..N] using periodicity ----
function grundy_counts_up_to(N_val: i64, g: ptr<i32>, pre: i32, period: i32, counts: ptr<i64>, max_g: i32) -> void {
let mut k: i32 = 0
while k < max_g {
counts[k] = 0
k = k + 1
}
if N_val <= 0 { return }
if N_val < (pre as i64) {
let mut n: i64 = 1
while n <= N_val {
counts[g[n]] = counts[g[n]] + 1
n = n + 1
}
return
}
let mut n: i32 = 1
while n < pre {
counts[g[n]] = counts[g[n]] + 1
n = n + 1
}
let per_counts: ptr<i64> = calloc(16, 8) as ptr<i64>
let mut pn: i32 = pre
while pn < pre + period {
per_counts[g[pn]] = per_counts[g[pn]] + 1
pn = pn + 1
}
let total_period_terms: i64 = N_val - (pre as i64) + 1
let q: i64 = total_period_terms / (period as i64)
let r: i64 = total_period_terms % (period as i64)
k = 0
while k < max_g {
counts[k] = counts[k] + per_counts[k] * q
k = k + 1
}
let mut rn: i64 = pre as i64
while rn < (pre as i64) + r {
counts[g[rn]] = counts[g[rn]] + 1
rn = rn + 1
}
free(per_counts as ptr<void>)
}
function S_mod(N_val: i64, m: i32, modv: i64, g: ptr<i32>, pre: i32, period: i32) -> i64 {
let max_g: i32 = 16
let counts: ptr<i64> = calloc(16, 8) as ptr<i64>
grundy_counts_up_to(N_val, g, pre, period, counts, max_g)
let pp_p: ptr<i64> = calloc(20, 8) as ptr<i64>
let pp_pe: ptr<i64> = calloc(20, 8) as ptr<i64>
let npp: i32 = factor_prime_powers(modv, pp_p, pp_pe)
let mods: ptr<i64> = calloc(20, 8) as ptr<i64>
let Ms: ptr<i64> = calloc(20, 8) as ptr<i64>
let inv_Ms: ptr<i64> = calloc(20, 8) as ptr<i64>
let mut i: i32 = 0
while i < npp {
mods[i] = pp_pe[i]
Ms[i] = modv / pp_pe[i]
inv_Ms[i] = inv_mod(Ms[i] % pp_pe[i], pp_pe[i])
i = i + 1
}
# allocate den table arrays
dt_p = calloc(20, 8) as ptr<i64>
dt_pe = calloc(20, 8) as ptr<i64>
dt_den_free = calloc(20, 8) as ptr<ptr<i64> >
dt_den_v = calloc(20, 8) as ptr<ptr<i32> >
dt_inv_free = calloc(20, 8) as ptr<ptr<i64> >
i = 0
while i < npp {
precompute_den_tables(i, pp_p[i], pp_pe[i], m)
i = i + 1
}
let inv16: i64 = inv_mod(16, modv)
let mut total: i64 = 0
let mut s: i32 = 0
while s < 16 {
let mut a: i64 = 0
let mut gv: i32 = 0
while gv < max_g {
if counts[gv] != 0 && (popcount(gv & s) & 1) == 0 {
a = a + counts[gv]
}
gv = gv + 1
}
# CRT combine
let mut x: i64 = 0
i = 0
while i < npp {
let resid: i64 = coeff_term_mod_prime_power(N_val, m, a, i)
x = (x + mulmod(mulmod(resid % mods[i], Ms[i], modv), inv_Ms[i], modv)) % modv
i = i + 1
}
total = (total + x) % modv
s = s + 1
}
# free den tables
i = 0
while i < npp {
free(dt_den_free[i] as ptr<void>)
free(dt_den_v[i] as ptr<void>)
free(dt_inv_free[i] as ptr<void>)
i = i + 1
}
free(dt_p as ptr<void>)
free(dt_pe as ptr<void>)
free(dt_den_free as ptr<void>)
free(dt_den_v as ptr<void>)
free(dt_inv_free as ptr<void>)
free(counts as ptr<void>)
free(pp_p as ptr<void>)
free(pp_pe as ptr<void>)
free(mods as ptr<void>)
free(Ms as ptr<void>)
free(inv_Ms as ptr<void>)
return mulmod(total, inv16, modv)
}
function main() -> i32 {
let precomp_limit: i32 = PRE + 2 * PERIOD
let g_fast: ptr<i32> = malloc(((precomp_limit + 1) as i64) * 4) as ptr<i32>
g_fast[0] = 0
compute_grundy(g_fast, precomp_limit, SPLIT_LIMIT)
let ans: i64 = S_mod(N_VAL, M_VAL, MOD, g_fast, PRE, PERIOD)
printf("%lld\n", ans)
free(g_fast as ptr<void>)
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 mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t powmod_i64_i64_i64(int64_t a0, int64_t e0, int64_t m);
int64_t inv_mod_i64_i64(int64_t a0, int64_t modv);
int32_t popcount_i32(int32_t x);
void strip_p_i64_i64_ptr_i64_ptr_i32(int64_t x, int64_t p, int64_t* x_free, int32_t* v);
int32_t factor_prime_powers_i64_ptr_i64_ptr_i64(int64_t n, int64_t* out_p, int64_t* out_pe);
void compute_grundy_ptr_i32_i32_i32(int32_t* g, int32_t limit, int32_t split_limit);
void precompute_den_tables_i32_i64_i64_i32(int32_t idx, int64_t p, int64_t pe, int32_t m);
int64_t coeff_term_mod_prime_power_i64_i32_i64_i32(int64_t N_val, int32_t m, int64_t a, int32_t idx);
void grundy_counts_up_to_i64_ptr_i32_i32_i32_ptr_i64_i32(int64_t N_val, int32_t* g, int32_t pre, int32_t period, int64_t* counts, int32_t max_g);
int64_t S_mod_i64_i32_i64_ptr_i32_i32_i32(int64_t N_val, int32_t m, int64_t modv, int32_t* g, int32_t pre, int32_t period);
int32_t main(void);
static const int64_t N_VAL = 12491249;
static const int32_t M_VAL = 1249;
static const int64_t MOD = 912491249;
static const int32_t PRE = 322;
static const int32_t PERIOD = 11060;
static const int32_t SPLIT_LIMIT = 600;
/* Module statics */
static int64_t* dt_p = NULL;
static int64_t* dt_pe = NULL;
static int64_t** dt_den_free = NULL;
static int32_t** dt_den_v = NULL;
static int64_t** dt_inv_free = NULL;
int64_t mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(m))))));
}
int64_t powmod_i64_i64_i64(int64_t a0, int64_t e0, int64_t m) {
int64_t r = FLOW_CHECKED_MOD((1), (m));
int64_t a = FLOW_CHECKED_MOD((a0), (m));
if (a < 0) {
a = (a + m);
}
int64_t e = e0;
while (e > 0) {
if ((e & 1) == 1) {
r = mulmod_i64_i64_i64(r, a, m);
}
a = mulmod_i64_i64_i64(a, a, m);
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t inv_mod_i64_i64(int64_t a0, int64_t modv) {
int64_t a = FLOW_CHECKED_MOD((a0), (modv));
if (a < 0) {
a = (a + modv);
}
int64_t x0 = 1;
int64_t x1 = 0;
int64_t aa = a;
int64_t mm = modv;
while (mm != 0) {
int64_t q = FLOW_CHECKED_DIV((aa), (mm));
int64_t t = (aa - (q * mm));
aa = mm;
mm = t;
int64_t t2 = (x0 - (q * x1));
x0 = x1;
x1 = t2;
}
if (aa != 1) {
return (-1);
}
int64_t result = FLOW_CHECKED_MOD((x0), (modv));
if (result < 0) {
result = (result + modv);
}
return result;
}
int32_t popcount_i32(int32_t x) {
int32_t n = 0;
int32_t v = x;
while (v != 0) {
n = (n + 1);
v = (v & (v - 1));
}
return n;
}
void strip_p_i64_i64_ptr_i64_ptr_i32(int64_t x, int64_t p, int64_t* x_free, int32_t* v) {
x_free[0] = x;
v[0] = 0;
while (FLOW_CHECKED_MOD((x_free[0]), (p)) == 0) {
x_free[0] = FLOW_CHECKED_DIV((x_free[0]), (p));
v[0] = (v[0] + 1);
}
}
int32_t factor_prime_powers_i64_ptr_i64_ptr_i64(int64_t n, int64_t* out_p, int64_t* out_pe) {
int32_t count = 0;
int64_t x = n;
int64_t p = 2;
while ((p * p) <= x) {
if (FLOW_CHECKED_MOD((x), (p)) == 0) {
int64_t pe = 1;
while (FLOW_CHECKED_MOD((x), (p)) == 0) {
x = FLOW_CHECKED_DIV((x), (p));
pe = (pe * p);
}
out_p[count] = p;
out_pe[count] = pe;
count = (count + 1);
}
if (p == 2) {
p = 3;
} else {
p = (p + 2);
}
}
if (x > 1) {
out_p[count] = x;
out_pe[count] = x;
count = (count + 1);
}
return count;
}
void compute_grundy_ptr_i32_i32_i32(int32_t* g, int32_t limit, int32_t split_limit) {
int32_t n = 1;
while (n <= limit) {
int32_t seen = 0;
if (n >= 1) {
seen = (seen | FLOW_CHECKED_SHL((1), (g[(n - 1)])));
}
if (n >= 2) {
seen = (seen | FLOW_CHECKED_SHL((1), (g[(n - 2)])));
}
if (n >= 4) {
seen = (seen | FLOW_CHECKED_SHL((1), (g[(n - 4)])));
}
if (n >= 9) {
seen = (seen | FLOW_CHECKED_SHL((1), (g[(n - 9)])));
}
int32_t max_i = (n - 1);
if ((split_limit > 0 && split_limit < (n - 1))) {
max_i = split_limit;
}
int32_t i = 1;
while (i <= max_i) {
seen = (seen | FLOW_CHECKED_SHL((1), ((g[i] ^ g[(n - i)]))));
i = (i + 1);
}
int32_t mex = 0;
while ((FLOW_CHECKED_SHR((seen), (mex)) & 1) == 1) {
mex = (mex + 1);
}
g[n] = mex;
n = (n + 1);
}
}
void precompute_den_tables_i32_i64_i64_i32(int32_t idx, int64_t p, int64_t pe, int32_t m) {
dt_p[idx] = p;
dt_pe[idx] = pe;
dt_den_free[idx] = ((int64_t*)(malloc((((int64_t)((m + 1))) * 8))));
dt_den_v[idx] = ((int32_t*)(malloc((((int64_t)((m + 1))) * 4))));
dt_inv_free[idx] = ((int64_t*)(malloc((((int64_t)((m + 1))) * 8))));
dt_den_free[idx][0] = 1;
dt_inv_free[idx][0] = 1;
int32_t i = 1;
while (i <= m) {
int64_t* xf_ptr = (int64_t*)(((int64_t*)(malloc(8))));
int32_t* v_ptr = (int32_t*)(((int32_t*)(malloc(4))));
strip_p_i64_i64_ptr_i64_ptr_i32(((int64_t)(i)), p, xf_ptr, v_ptr);
dt_den_free[idx][i] = xf_ptr[0];
dt_den_v[idx][i] = v_ptr[0];
dt_inv_free[idx][i] = inv_mod_i64_i64(FLOW_CHECKED_MOD((xf_ptr[0]), (pe)), pe);
free(((void*)(xf_ptr)));
free(((void*)(v_ptr)));
i = (i + 1);
}
}
int64_t coeff_term_mod_prime_power_i64_i32_i64_i32(int64_t N_val, int32_t m, int64_t a, int32_t idx) {
int64_t p = dt_p[idx];
int64_t pe = dt_pe[idx];
int64_t A = a;
int64_t B = (N_val - a);
int64_t* u = (int64_t*)(((int64_t*)(calloc(((int64_t)((m + 1))), 8))));
int64_t* w = (int64_t*)(((int64_t*)(calloc(((int64_t)((m + 1))), 8))));
u[0] = FLOW_CHECKED_MOD((1), (pe));
if (A != 0) {
int64_t res = FLOW_CHECKED_MOD((1), (pe));
int32_t exp = 0;
int32_t i = 1;
while (i <= m) {
int64_t num = ((A + ((int64_t)(i))) - 1);
int64_t* num_free_ptr = (int64_t*)(((int64_t*)(malloc(8))));
int32_t* v_num_ptr = (int32_t*)(((int32_t*)(malloc(4))));
strip_p_i64_i64_ptr_i64_ptr_i32(num, p, num_free_ptr, v_num_ptr);
exp = (exp + v_num_ptr[0]);
exp = (exp - dt_den_v[idx][i]);
res = mulmod_i64_i64_i64(res, FLOW_CHECKED_MOD((num_free_ptr[0]), (pe)), pe);
res = mulmod_i64_i64_i64(res, dt_inv_free[idx][i], pe);
u[i] = mulmod_i64_i64_i64(res, powmod_i64_i64_i64(p, ((int64_t)(exp)), pe), pe);
free(((void*)(num_free_ptr)));
free(((void*)(v_num_ptr)));
i = (i + 1);
}
}
w[0] = FLOW_CHECKED_MOD((1), (pe));
if (B != 0) {
int64_t res = FLOW_CHECKED_MOD((1), (pe));
int32_t exp = 0;
int32_t i = 1;
while (i <= m) {
int64_t num = ((B + ((int64_t)(i))) - 1);
int64_t* num_free_ptr = (int64_t*)(((int64_t*)(malloc(8))));
int32_t* v_num_ptr = (int32_t*)(((int32_t*)(malloc(4))));
strip_p_i64_i64_ptr_i64_ptr_i32(num, p, num_free_ptr, v_num_ptr);
exp = (exp + v_num_ptr[0]);
exp = (exp - dt_den_v[idx][i]);
res = mulmod_i64_i64_i64(res, FLOW_CHECKED_MOD((num_free_ptr[0]), (pe)), pe);
res = mulmod_i64_i64_i64(res, dt_inv_free[idx][i], pe);
int64_t val = mulmod_i64_i64_i64(res, powmod_i64_i64_i64(p, ((int64_t)(exp)), pe), pe);
if ((i & 1) == 1) {
val = FLOW_CHECKED_MOD(((pe - val)), (pe));
}
w[i] = val;
free(((void*)(num_free_ptr)));
free(((void*)(v_num_ptr)));
i = (i + 1);
}
}
int64_t out = 0;
int32_t i = 0;
while (i <= m) {
out = FLOW_CHECKED_MOD(((out + mulmod_i64_i64_i64(u[i], w[(m - i)], pe))), (pe));
i = (i + 1);
}
free(((void*)(u)));
free(((void*)(w)));
return out;
}
void grundy_counts_up_to_i64_ptr_i32_i32_i32_ptr_i64_i32(int64_t N_val, int32_t* g, int32_t pre, int32_t period, int64_t* counts, int32_t max_g) {
int32_t k = 0;
while (k < max_g) {
counts[k] = 0;
k = (k + 1);
}
if (N_val <= 0) {
return;
}
if (N_val < ((int64_t)(pre))) {
int64_t n = 1;
while (n <= N_val) {
counts[g[n]] = (counts[g[n]] + 1);
n = (n + 1);
}
return;
}
int32_t n = 1;
while (n < pre) {
counts[g[n]] = (counts[g[n]] + 1);
n = (n + 1);
}
int64_t* per_counts = (int64_t*)(((int64_t*)(calloc(16, 8))));
int32_t pn = pre;
while (pn < (pre + period)) {
per_counts[g[pn]] = (per_counts[g[pn]] + 1);
pn = (pn + 1);
}
int64_t total_period_terms = ((N_val - ((int64_t)(pre))) + 1);
int64_t q = FLOW_CHECKED_DIV((total_period_terms), (((int64_t)(period))));
int64_t r = FLOW_CHECKED_MOD((total_period_terms), (((int64_t)(period))));
k = 0;
while (k < max_g) {
counts[k] = (counts[k] + (per_counts[k] * q));
k = (k + 1);
}
int64_t rn = ((int64_t)(pre));
while (rn < (((int64_t)(pre)) + r)) {
counts[g[rn]] = (counts[g[rn]] + 1);
rn = (rn + 1);
}
free(((void*)(per_counts)));
}
int64_t S_mod_i64_i32_i64_ptr_i32_i32_i32(int64_t N_val, int32_t m, int64_t modv, int32_t* g, int32_t pre, int32_t period) {
int32_t max_g = 16;
int64_t* counts = (int64_t*)(((int64_t*)(calloc(16, 8))));
grundy_counts_up_to_i64_ptr_i32_i32_i32_ptr_i64_i32(N_val, g, pre, period, counts, max_g);
int64_t* pp_p = (int64_t*)(((int64_t*)(calloc(20, 8))));
int64_t* pp_pe = (int64_t*)(((int64_t*)(calloc(20, 8))));
int32_t npp = factor_prime_powers_i64_ptr_i64_ptr_i64(modv, pp_p, pp_pe);
int64_t* mods = (int64_t*)(((int64_t*)(calloc(20, 8))));
int64_t* Ms = (int64_t*)(((int64_t*)(calloc(20, 8))));
int64_t* inv_Ms = (int64_t*)(((int64_t*)(calloc(20, 8))));
int32_t i = 0;
while (i < npp) {
mods[i] = pp_pe[i];
Ms[i] = FLOW_CHECKED_DIV((modv), (pp_pe[i]));
inv_Ms[i] = inv_mod_i64_i64(FLOW_CHECKED_MOD((Ms[i]), (pp_pe[i])), pp_pe[i]);
i = (i + 1);
}
dt_p = ((int64_t*)(calloc(20, 8)));
dt_pe = ((int64_t*)(calloc(20, 8)));
dt_den_free = ((int64_t**)(calloc(20, 8)));
dt_den_v = ((int32_t**)(calloc(20, 8)));
dt_inv_free = ((int64_t**)(calloc(20, 8)));
i = 0;
while (i < npp) {
precompute_den_tables_i32_i64_i64_i32(i, pp_p[i], pp_pe[i], m);
i = (i + 1);
}
int64_t inv16 = inv_mod_i64_i64(16, modv);
int64_t total = 0;
int32_t s = 0;
while (s < 16) {
int64_t a = 0;
int32_t gv = 0;
while (gv < max_g) {
if ((counts[gv] != 0 && (popcount_i32((gv & s)) & 1) == 0)) {
a = (a + counts[gv]);
}
gv = (gv + 1);
}
int64_t x = 0;
i = 0;
while (i < npp) {
int64_t resid = coeff_term_mod_prime_power_i64_i32_i64_i32(N_val, m, a, i);
x = FLOW_CHECKED_MOD(((x + mulmod_i64_i64_i64(mulmod_i64_i64_i64(FLOW_CHECKED_MOD((resid), (mods[i])), Ms[i], modv), inv_Ms[i], modv))), (modv));
i = (i + 1);
}
total = FLOW_CHECKED_MOD(((total + x)), (modv));
s = (s + 1);
}
i = 0;
while (i < npp) {
free(((void*)(dt_den_free[i])));
free(((void*)(dt_den_v[i])));
free(((void*)(dt_inv_free[i])));
i = (i + 1);
}
free(((void*)(dt_p)));
free(((void*)(dt_pe)));
free(((void*)(dt_den_free)));
free(((void*)(dt_den_v)));
free(((void*)(dt_inv_free)));
free(((void*)(counts)));
free(((void*)(pp_p)));
free(((void*)(pp_pe)));
free(((void*)(mods)));
free(((void*)(Ms)));
free(((void*)(inv_Ms)));
return mulmod_i64_i64_i64(total, inv16, modv);
}
int32_t main(void) {
int32_t precomp_limit = (PRE + (2 * PERIOD));
int32_t* g_fast = (int32_t*)(((int32_t*)(malloc((((int64_t)((precomp_limit + 1))) * 4)))));
g_fast[0] = 0;
compute_grundy_ptr_i32_i32_i32(g_fast, precomp_limit, SPLIT_LIMIT);
int64_t ans = S_mod_i64_i32_i64_ptr_i32_i32_i32(N_VAL, M_VAL, MOD, g_fast, PRE, PERIOD);
printf("%lld\n", ans);
free(((void*)(g_fast)));
return 0;
}