Compute F(10^5) mod 1111124111, where F(n) counts compositions of n whose maximal runs of equal parts all have odd length. Uses NTT (Number Theoretic Transform) with 3 primes and CRT for exact polynomial multiplication, plus Newton iteration for series inversion. Pure Flow port of the native C solver.
# Project Euler 929: Odd-Run Compositions
# Compute F(10^5) mod 1111124111, where F(n) counts compositions of n
# whose maximal runs of equal parts all have odd length.
# Uses NTT (Number Theoretic Transform) with 3 primes and CRT
# for exact polynomial multiplication, plus Newton iteration for
# series inversion.
# Pure Flow port of the native C solver.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function realloc(p: ptr<void>, n: i64) -> ptr<void>
function printf(fmt: ptr<i8>, ...) -> i32
}
const MOD: i64 = 1111124111
const N: i32 = 100000
# NTT primes
const NTT_P0: i64 = 998244353
const NTT_P1: i64 = 1004535809
const NTT_P2: i64 = 754974721
const NTT_G0: i64 = 3
const NTT_G1: i64 = 3
const NTT_G2: i64 = 11
# CRT precomputed coefficients
let mut p1_mod_p2_inv: i64 = 0
let mut p12_mod_p3_inv: i64 = 0
let mut p1_mod_MOD: i64 = 0
let mut p12_mod_MOD: i64 = 0
# NTT bit-reversal
let mut ntt_rev: ptr<i32> = null as ptr<i32>
let mut ntt_rev_n: i32 = 0
function mulmod(a: i64, b: i64, mod: i64) -> i64 {
return ((a as i128) * (b as i128) % (mod as i128)) as i64
}
function powmod(a0: i64, e0: i64, mod: i64) -> i64 {
let mut r: i64 = 1 % mod
let mut a: i64 = a0 % mod
if a < 0 { a = a + mod }
let mut e: i64 = e0
while e > 0 {
if (e & 1) != 0 { r = mulmod(r, a, mod) }
a = mulmod(a, a, mod)
e = e >> 1
}
return r
}
function modinv(a: i64, mod: i64) -> i64 {
return powmod(a, mod - 2, mod)
}
function ntt_bitrev(n: i32) -> void {
if ntt_rev_n != n {
ntt_rev = (realloc(ntt_rev as ptr<void>, (n as i64) * 4)) as ptr<i32>
ntt_rev_n = n
}
let mut logn: i32 = 0
let mut tmp: i32 = n
while tmp > 1 {
logn = logn + 1
tmp = tmp >> 1
}
ntt_rev[0] = 0
let mut i: i32 = 1
while i < n {
ntt_rev[i] = (ntt_rev[i >> 1] >> 1) | ((i & 1) << (logn - 1))
i = i + 1
}
}
function ntt(a: ptr<i64>, n: i32, invert: i32, mod: i64, gen: i64) -> void {
let mut i: i32 = 0
while i < n {
let j: i32 = ntt_rev[i]
if i < j {
let t: i64 = a[i]
a[i] = a[j]
a[j] = t
}
i = i + 1
}
let mut len: i32 = 2
while len <= n {
let half: i32 = len >> 1
let mut w: i64 = 0
if invert != 0 {
w = powmod(gen, (mod - 1) - (mod - 1) / (len as i64), mod)
} else {
w = powmod(gen, (mod - 1) / (len as i64), mod)
}
let mut ii: i32 = 0
while ii < n {
let mut wk: i64 = 1
let mut jj: i32 = 0
while jj < half {
let u: i64 = a[ii + jj]
let v: i64 = mulmod(a[ii + jj + half], wk, mod)
a[ii + jj] = (u + v) % mod
a[ii + jj + half] = ((u - v) % mod + mod) % mod
wk = mulmod(wk, w, mod)
jj = jj + 1
}
ii = ii + len
}
len = len << 1
}
if invert != 0 {
let inv_n: i64 = modinv((n as i64), mod)
let mut iii: i32 = 0
while iii < n {
a[iii] = mulmod(a[iii], inv_n, mod)
iii = iii + 1
}
}
}
# Convolution mod MOD using 3-prime NTT + CRT.
# Returns result in a freshly allocated array of size `limit`.
function conv_mod(a: ptr<i64>, na: i32, b: ptr<i64>, nb: i32, limit0: i32) -> ptr<i64> {
if na == 0 || nb == 0 { return null as ptr<i64> }
let full_len: i32 = na + nb - 1
let mut limit: i32 = limit0
if limit > full_len { limit = full_len }
if limit <= 0 { return null as ptr<i64> }
# Small case: naive
if (na as i64) * (nb as i64) <= 16384 {
let res: ptr<i64> = (calloc((limit as i64), 8)) as ptr<i64>
let mut i: i32 = 0
while i < na {
if a[i] == 0 {
i = i + 1
continue
}
let mut maxj: i32 = nb
if limit - i < maxj { maxj = limit - i }
let mut j: i32 = 0
while j < maxj {
res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
if res[i + j] < 0 { res[i + j] = res[i + j] + MOD }
j = j + 1
}
i = i + 1
}
return res
}
let mut n_ntt: i32 = 1
while n_ntt < full_len {
n_ntt = n_ntt << 1
}
ntt_bitrev(n_ntt)
let res: ptr<i64> = (calloc((limit as i64), 8)) as ptr<i64>
# Compute NTT for each prime
let ntt_results: array<ptr<i64>, 3> = [null as ptr<i64>, null as ptr<i64>, null as ptr<i64>]
let ntt_primes: array<i64, 3> = [NTT_P0, NTT_P1, NTT_P2]
let ntt_gens: array<i64, 3> = [NTT_G0, NTT_G1, NTT_G2]
let mut pi: i32 = 0
while pi < 3 {
let mod: i64 = ntt_primes[pi]
let gen: i64 = ntt_gens[pi]
let fa: ptr<i64> = (calloc((n_ntt as i64), 8)) as ptr<i64>
let fb: ptr<i64> = (calloc((n_ntt as i64), 8)) as ptr<i64>
let mut i: i32 = 0
while i < na {
fa[i] = a[i] % mod
i = i + 1
}
i = 0
while i < nb {
fb[i] = b[i] % mod
i = i + 1
}
ntt(fa, n_ntt, 0, mod, gen)
ntt(fb, n_ntt, 0, mod, gen)
let mut ii: i32 = 0
while ii < n_ntt {
fa[ii] = mulmod(fa[ii], fb[ii], mod)
ii = ii + 1
}
ntt(fa, n_ntt, 1, mod, gen)
ntt_results[pi] = fa
free(fb as ptr<void>)
pi = pi + 1
}
# CRT via Garner's algorithm
let mut i: i32 = 0
while i < limit {
let a1: i64 = ntt_results[0][i]
let a2: i64 = ntt_results[1][i]
let a3: i64 = ntt_results[2][i]
# Step 2: x mod p1*p2
let mut t2: i64 = ((a2 - a1) % NTT_P1 + NTT_P1) % NTT_P1
t2 = mulmod(t2, p1_mod_p2_inv, NTT_P1)
let x12_mod: i64 = (a1 % MOD + mulmod(p1_mod_MOD, t2 % MOD, MOD)) % MOD
# Step 3: x mod p1*p2*p3
let mut x12_mod_p3: i64 = (a1 % NTT_P2 + mulmod(NTT_P0 % NTT_P2, t2, NTT_P2)) % NTT_P2
if x12_mod_p3 < 0 { x12_mod_p3 = x12_mod_p3 + NTT_P2 }
let mut t3: i64 = ((a3 - x12_mod_p3) % NTT_P2 + NTT_P2) % NTT_P2
t3 = mulmod(t3, p12_mod_p3_inv, NTT_P2)
res[i] = (x12_mod + mulmod(p12_mod_MOD, t3 % MOD, MOD)) % MOD
if res[i] < 0 { res[i] = res[i] + MOD }
i = i + 1
}
free(ntt_results[0] as ptr<void>)
free(ntt_results[1] as ptr<void>)
free(ntt_results[2] as ptr<void>)
return res
}
# Series inversion via Newton iteration.
function series_inverse(f: ptr<i64>, n_terms: i32) -> ptr<i64> {
if n_terms <= 0 { return null as ptr<i64> }
let mut f0: i64 = f[0] % MOD
if f0 < 0 { f0 = f0 + MOD }
let g0: i64 = modinv(f0, MOD)
let g: ptr<i64> = (calloc((n_terms as i64), 8)) as ptr<i64>
g[0] = g0
let mut m: i32 = 1
while m < n_terms {
let mut m2: i32 = m * 2
if m2 > n_terms { m2 = n_terms }
let fg: ptr<i64> = conv_mod(f, m2, g, m, m2)
let mut i: i32 = 0
while i < m2 {
fg[i] = (-fg[i]) % MOD
if fg[i] < 0 { fg[i] = fg[i] + MOD }
i = i + 1
}
fg[0] = (fg[0] + 2) % MOD
let g_new: ptr<i64> = conv_mod(g, m, fg, m2, m2)
let mut ii: i32 = 0
while ii < m2 {
g[ii] = g_new[ii]
ii = ii + 1
}
free(fg as ptr<void>)
free(g_new as ptr<void>)
m = m2
}
return g
}
function init_crt() -> void {
p1_mod_p2_inv = modinv(NTT_P0 % NTT_P1, NTT_P1)
let p12_mod_p3: i64 = mulmod(NTT_P0 % NTT_P2, NTT_P1 % NTT_P2, NTT_P2)
p12_mod_p3_inv = modinv(p12_mod_p3, NTT_P2)
p1_mod_MOD = NTT_P0 % MOD
p12_mod_MOD = mulmod(NTT_P0 % MOD, NTT_P1 % MOD, MOD)
}
function main() -> i32 {
init_crt()
# Fibonacci numbers mod MOD
let fib: ptr<i64> = (calloc((N + 1) as i64, 8)) as ptr<i64>
fib[1] = 1
if N >= 2 { fib[2] = 1 }
let mut i: i32 = 3
while i <= N {
let mut x: i64 = fib[i - 1] + fib[i - 2]
if x >= MOD { x = x - MOD }
fib[i] = x
i = i + 1
}
# Sieve: s[n] = sum_{d|n} (-1)^(d-1) * Fib[d] mod MOD
let s: ptr<i64> = (calloc((N + 1) as i64, 8)) as ptr<i64>
let mut d: i32 = 1
while d <= N {
let mut val: i64 = fib[d]
if (d & 1) == 0 { val = MOD - val }
let mut k: i32 = d
while k <= N {
let mut x: i64 = s[k] + val
if x >= MOD { x = x - MOD }
s[k] = x
k = k + d
}
d = d + 1
}
# f(x) = 1 - S(x)
let f: ptr<i64> = (calloc((N + 1) as i64, 8)) as ptr<i64>
f[0] = 1
let mut ii: i32 = 1
while ii <= N {
f[ii] = (MOD - s[ii]) % MOD
if f[ii] < 0 { f[ii] = f[ii] + MOD }
ii = ii + 1
}
# t = 1 / f
let t: ptr<i64> = series_inverse(f, N + 1)
let mut result: i64 = t[N] % MOD
if result < 0 { result = result + MOD }
free(fib as ptr<void>)
free(s as ptr<void>)
free(f as ptr<void>)
free(t as ptr<void>)
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; }
int64_t mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t mod);
int64_t powmod_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod);
int64_t modinv_i64_i64(int64_t a, int64_t mod);
void ntt_bitrev_i32(int32_t n);
void ntt_ptr_i64_i32_i32_i64_i64(int64_t* a, int32_t n, int32_t invert, int64_t mod, int64_t gen);
int64_t* conv_mod_ptr_i64_i32_ptr_i64_i32_i32(int64_t* a, int32_t na, int64_t* b, int32_t nb, int32_t limit0);
int64_t* series_inverse_ptr_i64_i32(int64_t* f, int32_t n_terms);
void init_crt(void);
int32_t main(void);
static const int64_t MOD = 1111124111;
static const int32_t N = 100000;
static const int64_t NTT_P0 = 998244353;
static const int64_t NTT_P1 = 1004535809;
static const int64_t NTT_P2 = 754974721;
static const int64_t NTT_G0 = 3;
static const int64_t NTT_G1 = 3;
static const int64_t NTT_G2 = 11;
/* Module statics */
static int64_t p1_mod_p2_inv = 0;
static int64_t p12_mod_p3_inv = 0;
static int64_t p1_mod_MOD = 0;
static int64_t p12_mod_MOD = 0;
static int32_t* ntt_rev = ((int32_t*)(NULL));
static int32_t ntt_rev_n = 0;
int64_t mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t mod) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(mod))))));
}
int64_t powmod_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod) {
int64_t r = FLOW_CHECKED_MOD((1), (mod));
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
if (a < 0) {
a = (a + mod);
}
int64_t e = e0;
while (e > 0) {
if ((e & 1) != 0) {
r = mulmod_i64_i64_i64(r, a, mod);
}
a = mulmod_i64_i64_i64(a, a, mod);
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t modinv_i64_i64(int64_t a, int64_t mod) {
return powmod_i64_i64_i64(a, (mod - 2), mod);
}
void ntt_bitrev_i32(int32_t n) {
if (ntt_rev_n != n) {
ntt_rev = ((int32_t*)(realloc(((void*)(ntt_rev)), (((int64_t)(n)) * 4))));
ntt_rev_n = n;
}
int32_t logn = 0;
int32_t tmp = n;
while (tmp > 1) {
logn = (logn + 1);
tmp = FLOW_CHECKED_SHR((tmp), (1));
}
ntt_rev[0] = 0;
int32_t i = 1;
while (i < n) {
ntt_rev[i] = (FLOW_CHECKED_SHR((ntt_rev[FLOW_CHECKED_SHR((i), (1))]), (1)) | FLOW_CHECKED_SHL(((i & 1)), ((logn - 1))));
i = (i + 1);
}
}
void ntt_ptr_i64_i32_i32_i64_i64(int64_t* a, int32_t n, int32_t invert, int64_t mod, int64_t gen) {
int32_t i = 0;
while (i < n) {
int32_t j = ntt_rev[i];
if (i < j) {
int64_t t = a[i];
a[i] = a[j];
a[j] = t;
}
i = (i + 1);
}
int32_t len = 2;
while (len <= n) {
int32_t half = FLOW_CHECKED_SHR((len), (1));
int64_t w = 0;
if (invert != 0) {
w = powmod_i64_i64_i64(gen, ((mod - 1) - FLOW_CHECKED_DIV(((mod - 1)), (((int64_t)(len))))), mod);
} else {
w = powmod_i64_i64_i64(gen, FLOW_CHECKED_DIV(((mod - 1)), (((int64_t)(len)))), mod);
}
int32_t ii = 0;
while (ii < n) {
int64_t wk = 1;
int32_t jj = 0;
while (jj < half) {
int64_t u = a[(ii + jj)];
int64_t v = mulmod_i64_i64_i64(a[((ii + jj) + half)], wk, mod);
a[(ii + jj)] = FLOW_CHECKED_MOD(((u + v)), (mod));
a[((ii + jj) + half)] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((u - v)), (mod)) + mod)), (mod));
wk = mulmod_i64_i64_i64(wk, w, mod);
jj = (jj + 1);
}
ii = (ii + len);
}
len = FLOW_CHECKED_SHL((len), (1));
}
if (invert != 0) {
int64_t inv_n = modinv_i64_i64(((int64_t)(n)), mod);
int32_t iii = 0;
while (iii < n) {
a[iii] = mulmod_i64_i64_i64(a[iii], inv_n, mod);
iii = (iii + 1);
}
}
}
int64_t* conv_mod_ptr_i64_i32_ptr_i64_i32_i32(int64_t* a, int32_t na, int64_t* b, int32_t nb, int32_t limit0) {
if ((na == 0 || nb == 0)) {
return ((int64_t*)(NULL));
}
int32_t full_len = ((na + nb) - 1);
int32_t limit = limit0;
if (limit > full_len) {
limit = full_len;
}
if (limit <= 0) {
return ((int64_t*)(NULL));
}
if ((((int64_t)(na)) * ((int64_t)(nb))) <= 16384) {
int64_t* res = (int64_t*)(((int64_t*)(calloc(((int64_t)(limit)), 8))));
int32_t i = 0;
while (i < na) {
if (a[i] == 0) {
i = (i + 1);
continue;
}
int32_t maxj = nb;
if ((limit - i) < maxj) {
maxj = (limit - i);
}
int32_t j = 0;
while (j < maxj) {
res[(i + j)] = FLOW_CHECKED_MOD(((res[(i + j)] + (a[i] * b[j]))), (MOD));
if (res[(i + j)] < 0) {
res[(i + j)] = (res[(i + j)] + MOD);
}
j = (j + 1);
}
i = (i + 1);
}
return res;
}
int32_t n_ntt = 1;
while (n_ntt < full_len) {
n_ntt = FLOW_CHECKED_SHL((n_ntt), (1));
}
ntt_bitrev_i32(n_ntt);
int64_t* res = (int64_t*)(((int64_t*)(calloc(((int64_t)(limit)), 8))));
int64_t* ntt_results[3] = { ((int64_t*)(NULL)), ((int64_t*)(NULL)), ((int64_t*)(NULL)) };
int64_t ntt_primes[3] = { NTT_P0, NTT_P1, NTT_P2 };
int64_t ntt_gens[3] = { NTT_G0, NTT_G1, NTT_G2 };
int32_t pi = 0;
while (pi < 3) {
int64_t mod = (((unsigned)(pi) < 3) ? ntt_primes[pi] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(pi), 3), flow_fault_handler("array index out of bounds"), ntt_primes[0]));
int64_t gen = (((unsigned)(pi) < 3) ? ntt_gens[pi] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(pi), 3), flow_fault_handler("array index out of bounds"), ntt_gens[0]));
int64_t* fa = (int64_t*)(((int64_t*)(calloc(((int64_t)(n_ntt)), 8))));
int64_t* fb = (int64_t*)(((int64_t*)(calloc(((int64_t)(n_ntt)), 8))));
int32_t i = 0;
while (i < na) {
fa[i] = FLOW_CHECKED_MOD((a[i]), (mod));
i = (i + 1);
}
i = 0;
while (i < nb) {
fb[i] = FLOW_CHECKED_MOD((b[i]), (mod));
i = (i + 1);
}
ntt_ptr_i64_i32_i32_i64_i64(fa, n_ntt, 0, mod, gen);
ntt_ptr_i64_i32_i32_i64_i64(fb, n_ntt, 0, mod, gen);
int32_t ii = 0;
while (ii < n_ntt) {
fa[ii] = mulmod_i64_i64_i64(fa[ii], fb[ii], mod);
ii = (ii + 1);
}
ntt_ptr_i64_i32_i32_i64_i64(fa, n_ntt, 1, mod, gen);
ntt_results[pi] = fa;
free(((void*)(fb)));
pi = (pi + 1);
}
int32_t i = 0;
while (i < limit) {
int64_t a1 = (((unsigned)(0) < 3) ? ntt_results[0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(0), 3), flow_fault_handler("array index out of bounds"), ntt_results[0]))[i];
int64_t a2 = (((unsigned)(1) < 3) ? ntt_results[1] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(1), 3), flow_fault_handler("array index out of bounds"), ntt_results[0]))[i];
int64_t a3 = (((unsigned)(2) < 3) ? ntt_results[2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(2), 3), flow_fault_handler("array index out of bounds"), ntt_results[0]))[i];
int64_t t2 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((a2 - a1)), (NTT_P1)) + NTT_P1)), (NTT_P1));
t2 = mulmod_i64_i64_i64(t2, p1_mod_p2_inv, NTT_P1);
int64_t x12_mod = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a1), (MOD)) + mulmod_i64_i64_i64(p1_mod_MOD, FLOW_CHECKED_MOD((t2), (MOD)), MOD))), (MOD));
int64_t x12_mod_p3 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((a1), (NTT_P2)) + mulmod_i64_i64_i64(FLOW_CHECKED_MOD((NTT_P0), (NTT_P2)), t2, NTT_P2))), (NTT_P2));
if (x12_mod_p3 < 0) {
x12_mod_p3 = (x12_mod_p3 + NTT_P2);
}
int64_t t3 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((a3 - x12_mod_p3)), (NTT_P2)) + NTT_P2)), (NTT_P2));
t3 = mulmod_i64_i64_i64(t3, p12_mod_p3_inv, NTT_P2);
res[i] = FLOW_CHECKED_MOD(((x12_mod + mulmod_i64_i64_i64(p12_mod_MOD, FLOW_CHECKED_MOD((t3), (MOD)), MOD))), (MOD));
if (res[i] < 0) {
res[i] = (res[i] + MOD);
}
i = (i + 1);
}
free(((void*)((((unsigned)(0) < 3) ? ntt_results[0] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(0), 3), flow_fault_handler("array index out of bounds"), ntt_results[0])))));
free(((void*)((((unsigned)(1) < 3) ? ntt_results[1] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(1), 3), flow_fault_handler("array index out of bounds"), ntt_results[0])))));
free(((void*)((((unsigned)(2) < 3) ? ntt_results[2] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(2), 3), flow_fault_handler("array index out of bounds"), ntt_results[0])))));
return res;
}
int64_t* series_inverse_ptr_i64_i32(int64_t* f, int32_t n_terms) {
if (n_terms <= 0) {
return ((int64_t*)(NULL));
}
int64_t f0 = FLOW_CHECKED_MOD((f[0]), (MOD));
if (f0 < 0) {
f0 = (f0 + MOD);
}
int64_t g0 = modinv_i64_i64(f0, MOD);
int64_t* g = (int64_t*)(((int64_t*)(calloc(((int64_t)(n_terms)), 8))));
g[0] = g0;
int32_t m = 1;
while (m < n_terms) {
int32_t m2 = (m * 2);
if (m2 > n_terms) {
m2 = n_terms;
}
int64_t* fg = (int64_t*)(conv_mod_ptr_i64_i32_ptr_i64_i32_i32(f, m2, g, m, m2));
int32_t i = 0;
while (i < m2) {
fg[i] = FLOW_CHECKED_MOD(((-fg[i])), (MOD));
if (fg[i] < 0) {
fg[i] = (fg[i] + MOD);
}
i = (i + 1);
}
fg[0] = FLOW_CHECKED_MOD(((fg[0] + 2)), (MOD));
int64_t* g_new = (int64_t*)(conv_mod_ptr_i64_i32_ptr_i64_i32_i32(g, m, fg, m2, m2));
int32_t ii = 0;
while (ii < m2) {
g[ii] = g_new[ii];
ii = (ii + 1);
}
free(((void*)(fg)));
free(((void*)(g_new)));
m = m2;
}
return g;
}
void init_crt(void) {
p1_mod_p2_inv = modinv_i64_i64(FLOW_CHECKED_MOD((NTT_P0), (NTT_P1)), NTT_P1);
int64_t p12_mod_p3 = mulmod_i64_i64_i64(FLOW_CHECKED_MOD((NTT_P0), (NTT_P2)), FLOW_CHECKED_MOD((NTT_P1), (NTT_P2)), NTT_P2);
p12_mod_p3_inv = modinv_i64_i64(p12_mod_p3, NTT_P2);
p1_mod_MOD = FLOW_CHECKED_MOD((NTT_P0), (MOD));
p12_mod_MOD = mulmod_i64_i64_i64(FLOW_CHECKED_MOD((NTT_P0), (MOD)), FLOW_CHECKED_MOD((NTT_P1), (MOD)), MOD);
}
int32_t main(void) {
init_crt();
int64_t* fib = (int64_t*)(((int64_t*)(calloc(((int64_t)((N + 1))), 8))));
fib[1] = 1;
if (N >= 2) {
fib[2] = 1;
}
int32_t i = 3;
while (i <= N) {
int64_t x = (fib[(i - 1)] + fib[(i - 2)]);
if (x >= MOD) {
x = (x - MOD);
}
fib[i] = x;
i = (i + 1);
}
int64_t* s = (int64_t*)(((int64_t*)(calloc(((int64_t)((N + 1))), 8))));
int32_t d = 1;
while (d <= N) {
int64_t val = fib[d];
if ((d & 1) == 0) {
val = (MOD - val);
}
int32_t k = d;
while (k <= N) {
int64_t x = (s[k] + val);
if (x >= MOD) {
x = (x - MOD);
}
s[k] = x;
k = (k + d);
}
d = (d + 1);
}
int64_t* f = (int64_t*)(((int64_t*)(calloc(((int64_t)((N + 1))), 8))));
f[0] = 1;
int32_t ii = 1;
while (ii <= N) {
f[ii] = FLOW_CHECKED_MOD(((MOD - s[ii])), (MOD));
if (f[ii] < 0) {
f[ii] = (f[ii] + MOD);
}
ii = (ii + 1);
}
int64_t* t = (int64_t*)(series_inverse_ptr_i64_i32(f, (N + 1)));
int64_t result = FLOW_CHECKED_MOD((t[N]), (MOD));
if (result < 0) {
result = (result + MOD);
}
free(((void*)(fib)));
free(((void*)(s)));
free(((void*)(f)));
free(((void*)(t)));
printf("%lld\n", result);
return 0;
}