# Project Euler 559
# Permuted Matrices — factorial powers + series inversion.
# Ported from C to pure Flow. MOD = 1000000123.
import euler.nt { mod_pow }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const MOD: i64 = 1000000123
const P1: i64 = 998244353
const P2: i64 = 1004535809
const P3: i64 = 469762049
let mut g_inv_p1_mod_p2: i64 = -1
let mut g_inv_p12_mod_p3: i64 = -1
let mut g_P12: i128 = 0
function mod_inv(a: i64, mod: i64) -> i64 {
return mod_pow(a, mod - 2, mod)
}
function ntt(a: ptr<i64>, n: i64, invert: i32, mod: i64, root: i64) -> void {
let mut j: i64 = 0
let mut i: i64 = 1
while i < n {
let mut bit: i64 = n >> 1
while (j & bit) != 0 {
j = j ^ bit
bit = bit >> 1
}
j = j ^ bit
if i < j {
let tmp: i64 = a[i]
a[i] = a[j]
a[j] = tmp
}
i = i + 1
}
let mut length: i64 = 2
while length <= n {
let wlen: i64 = mod_pow(root, (mod - 1) / length, mod)
let mut wl: i64 = wlen
if invert == 1 { wl = mod_pow(wlen, mod - 2, mod) }
let half: i64 = length >> 1
i = 0
while i < n {
let mut w: i64 = 1
let mut jj: i64 = 0
while jj < half {
let u: i64 = a[i + jj]
let v: i64 = ((a[i + jj + half] as i128) * (w as i128) % (mod as i128)) as i64
let mut x: i64 = u + v
if x >= mod { x = x - mod }
let mut y: i64 = u - v
if y < 0 { y = y + mod }
a[i + jj] = x
a[i + jj + half] = y
w = ((w as i128) * (wl as i128) % (mod as i128)) as i64
jj = jj + 1
}
i = i + length
}
length = length << 1
}
if invert == 1 {
let inv_n: i64 = mod_pow(n, mod - 2, mod)
i = 0
while i < n {
a[i] = ((a[i] as i128) * (inv_n as i128) % (mod as i128)) as i64
i = i + 1
}
}
}
function convolve_one(a: ptr<i64>, n1: i64, b: ptr<i64>, n2: i64, mod: i64, root: i64, out_n: ptr<i64>) -> ptr<i64> {
let need: i64 = n1 + n2 - 1
let mut n: i64 = 1
while n < need { n = n << 1 }
let fa: ptr<i64> = calloc(n, 8) as ptr<i64>
let fb: ptr<i64> = calloc(n, 8) as ptr<i64>
let mut i: i64 = 0
while i < n1 { fa[i] = a[i] % mod; i = i + 1 }
i = 0
while i < n2 { fb[i] = b[i] % mod; i = i + 1 }
ntt(fa, n, 0, mod, root)
ntt(fb, n, 0, mod, root)
i = 0
while i < n {
fa[i] = ((fa[i] as i128) * (fb[i] as i128) % (mod as i128)) as i64
i = i + 1
}
ntt(fa, n, 1, mod, root)
out_n[0] = need
let res: ptr<i64> = malloc(need * 8) as ptr<i64>
i = 0
while i < need { res[i] = fa[i]; i = i + 1 }
free(fa as ptr<void>)
free(fb as ptr<void>)
return res
}
function crt3(a1: i64, a2: i64, a3: i64) -> i64 {
if g_inv_p1_mod_p2 < 0 {
g_inv_p1_mod_p2 = mod_inv(P1 % P2, P2)
g_P12 = (P1 as i128) * (P2 as i128)
g_inv_p12_mod_p3 = mod_inv((g_P12 % (P3 as i128)) as i64, P3)
}
let mut t1: i64 = ((a2 - a1) % P2)
if t1 < 0 { t1 = t1 + P2 }
t1 = ((t1 as i128) * (g_inv_p1_mod_p2 as i128) % (P2 as i128)) as i64
let x2: i128 = (a1 as i128) + (P1 as i128) * (t1 as i128)
let mut t2: i64 = ((a3 - (x2 % (P3 as i128)) as i64) % P3)
if t2 < 0 { t2 = t2 + P3 }
t2 = ((t2 as i128) * (g_inv_p12_mod_p3 as i128) % (P3 as i128)) as i64
let x: i128 = x2 + g_P12 * (t2 as i128)
let mut r: i64 = (x % (MOD as i128)) as i64
if r < 0 { r = r + MOD }
return r
}
function convolve_mod(a: ptr<i64>, n1: i64, b: ptr<i64>, n2: i64, out_n: ptr<i64>) -> ptr<i64> {
if n1 == 0 || n2 == 0 { out_n[0] = 0; return null as ptr<i64> }
let o1p: ptr<i64> = calloc(1, 8) as ptr<i64>
let o2p: ptr<i64> = calloc(1, 8) as ptr<i64>
let o3p: ptr<i64> = calloc(1, 8) as ptr<i64>
let c1: ptr<i64> = convolve_one(a, n1, b, n2, P1, 3, o1p)
let c2: ptr<i64> = convolve_one(a, n1, b, n2, P2, 3, o2p)
let c3: ptr<i64> = convolve_one(a, n1, b, n2, P3, 3, o3p)
let need: i64 = n1 + n2 - 1
let res: ptr<i64> = malloc(need * 8) as ptr<i64>
let mut i: i64 = 0
while i < need { res[i] = crt3(c1[i], c2[i], c3[i]); i = i + 1 }
free(c1 as ptr<void>)
free(c2 as ptr<void>)
free(c3 as ptr<void>)
free(o1p as ptr<void>)
free(o2p as ptr<void>)
free(o3p as ptr<void>)
out_n[0] = need
return res
}
function poly_mul_mod(A: ptr<i64>, n: i64, B: ptr<i64>, m: i64) -> ptr<i64> {
if n * m <= 40000 || n < 40 || m < 40 {
let res: ptr<i64> = calloc(n + m - 1, 8) as ptr<i64>
let mut i: i64 = 0
while i < n {
if A[i] != 0 {
let mut j: i64 = 0
while j < m {
res[i + j] = (res[i + j] + ((A[i] as i128) * (B[j] as i128) % (MOD as i128)) as i64) % MOD
j = j + 1
}
}
i = i + 1
}
return res
}
let onp: ptr<i64> = calloc(1, 8) as ptr<i64>
let r: ptr<i64> = convolve_mod(A, n, B, m, onp)
free(onp as ptr<void>)
return r
}
function poly_inv_mod(f: ptr<i64>, n: i64) -> ptr<i64> {
let mut g: ptr<i64> = calloc(n, 8) as ptr<i64>
g[0] = mod_inv(f[0], MOD)
let mut m: i64 = 1
while m < n {
let m2: i64 = m * 2
let mut m2c: i64 = m2
if m2c > n { m2c = n }
let fg: ptr<i64> = poly_mul_mod(f, m2c, g, m)
let h: ptr<i64> = calloc(m2c, 8) as ptr<i64>
let fglen: i64 = m2c + m - 1
let mut i: i64 = 0
while i < m2c {
let v: i64 = if i < fglen { fg[i] } else { 0 }
h[i] = (MOD - v) % MOD
i = i + 1
}
h[0] = (h[0] + 2) % MOD
free(fg as ptr<void>)
let ng: ptr<i64> = poly_mul_mod(g, m, h, m2c)
free(g as ptr<void>)
free(h as ptr<void>)
let gnew: ptr<i64> = calloc(m2c, 8) as ptr<i64>
let nglen: i64 = m + m2c - 1
i = 0
while i < m2c {
gnew[i] = if i < nglen { ng[i] } else { 0 }
i = i + 1
}
free(ng as ptr<void>)
g = gnew
m = m2c
}
return g
}
function pre_fac_pow(n: i64, r: i64, fac_pow: ptr<i64>, inv_fac_pow: ptr<i64>) -> void {
fac_pow[0] = 1
let mut i: i64 = 1
while i <= n {
let ip: i64 = mod_pow(i, r, MOD)
fac_pow[i] = ((fac_pow[i - 1] as i128) * (ip as i128) % (MOD as i128)) as i64
i = i + 1
}
inv_fac_pow[n] = mod_inv(fac_pow[n], MOD)
i = n - 1
while i >= 0 {
let ip: i64 = mod_pow(i + 1, r, MOD)
inv_fac_pow[i] = ((inv_fac_pow[i + 1] as i128) * (ip as i128) % (MOD as i128)) as i64
i = i - 1
}
}
function P_via_dp(k: i64, n: i64, fac_pow: ptr<i64>, inv_fac_pow: ptr<i64>) -> i64 {
let q: i64 = n / k
let rem: i64 = n % k
let m: i64 = q + (if rem != 0 { 1 } else { 0 })
let blocks: ptr<i64> = malloc(m * 8) as ptr<i64>
let mut i: i64 = 0
while i < q { blocks[i] = k; i = i + 1 }
if rem != 0 { blocks[q] = rem }
let f: ptr<i64> = calloc(m + 1, 8) as ptr<i64>
f[0] = fac_pow[n]
i = 1
while i <= m {
let mut seg: i64 = 0
let mut acc: i64 = 0
let mut j: i64 = i - 1
while j >= 0 {
seg = seg + blocks[j]
let term: i64 = ((f[j] as i128) * (inv_fac_pow[seg] as i128) % (MOD as i128)) as i64
if (i - j) % 2 == 1 { acc = acc + term } else { acc = acc - term }
j = j - 1
}
acc = acc % MOD
if acc < 0 { acc = acc + MOD }
f[i] = acc
i = i + 1
}
let ans: i64 = f[m]
free(blocks as ptr<void>)
free(f as ptr<void>)
return ans
}
function P_via_inverse(k: i64, n: i64, fac_pow: ptr<i64>, inv_fac_pow: ptr<i64>) -> i64 {
let q: i64 = n / k
let rem: i64 = n % k
let p: ptr<i64> = calloc(q + 1, 8) as ptr<i64>
p[0] = 1
let mut d: i64 = 1
while d <= q {
let mut coeff: i64 = inv_fac_pow[d * k]
if d % 2 == 1 { coeff = (MOD - coeff) % MOD }
p[d] = coeff
d = d + 1
}
let s: ptr<i64> = poly_inv_mod(p, q + 1)
let g0: i64 = fac_pow[n]
let g: ptr<i64> = malloc((q + 1) * 8) as ptr<i64>
let mut i: i64 = 0
while i <= q {
g[i] = ((g0 as i128) * (s[i] as i128) % (MOD as i128)) as i64
i = i + 1
}
if rem == 0 {
let a2: i64 = g[q]
free(p as ptr<void>)
free(s as ptr<void>)
free(g as ptr<void>)
return a2
}
let mut ans: i64 = 0
i = 0
while i <= q {
let seg_len: i64 = (q - i) * k + rem
let term: i64 = ((g[i] as i128) * (inv_fac_pow[seg_len] as i128) % (MOD as i128)) as i64
if (q - i) % 2 == 1 { ans = ans - term } else { ans = ans + term }
i = i + 1
}
let mut a3: i64 = ans % MOD
if a3 < 0 { a3 = a3 + MOD }
free(p as ptr<void>)
free(s as ptr<void>)
free(g as ptr<void>)
return a3
}
function Qn(n: i64) -> i64 {
let r: i64 = n
let fac_pow: ptr<i64> = malloc((n + 1) * 8) as ptr<i64>
let inv_fac_pow: ptr<i64> = malloc((n + 1) * 8) as ptr<i64>
pre_fac_pow(n, r, fac_pow, inv_fac_pow)
let k_inv_max: i64 = n / 200
let mut ans: i64 = 0
let mut k: i64 = 1
while k <= n {
let q: i64 = n / k
let v: i64 = 0
if k <= k_inv_max && q > 200 {
v = P_via_inverse(k, n, fac_pow, inv_fac_pow)
} else {
v = P_via_dp(k, n, fac_pow, inv_fac_pow)
}
ans = ans + v
if ans >= MOD { ans = ans - MOD }
k = k + 1
}
free(fac_pow as ptr<void>)
free(inv_fac_pow as ptr<void>)
return ans
}
function main() -> i32 {
printf("%lld\n", Qn(50000))
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 gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t mod_inv_i64_i64(int64_t a, int64_t mod);
void ntt_ptr_i64_i64_i32_i64_i64(int64_t* a, int64_t n, int32_t invert, int64_t mod, int64_t root);
int64_t* convolve_one_ptr_i64_i64_ptr_i64_i64_i64_i64_ptr_i64(int64_t* a, int64_t n1, int64_t* b, int64_t n2, int64_t mod, int64_t root, int64_t* out_n);
int64_t crt3_i64_i64_i64(int64_t a1, int64_t a2, int64_t a3);
int64_t* convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(int64_t* a, int64_t n1, int64_t* b, int64_t n2, int64_t* out_n);
int64_t* poly_mul_mod_ptr_i64_i64_ptr_i64_i64(int64_t* A, int64_t n, int64_t* B, int64_t m);
int64_t* poly_inv_mod_ptr_i64_i64(int64_t* f, int64_t n);
void pre_fac_pow_i64_i64_ptr_i64_ptr_i64(int64_t n, int64_t r, int64_t* fac_pow, int64_t* inv_fac_pow);
int64_t P_via_dp_i64_i64_ptr_i64_ptr_i64(int64_t k, int64_t n, int64_t* fac_pow, int64_t* inv_fac_pow);
int64_t P_via_inverse_i64_i64_ptr_i64_ptr_i64(int64_t k, int64_t n, int64_t* fac_pow, int64_t* inv_fac_pow);
int64_t Qn_i64(int64_t n);
int32_t main(void);
static const int64_t MOD = 1000000123;
static const int64_t P1 = 998244353;
static const int64_t P2 = 1004535809;
static const int64_t P3 = 469762049;
/* Module statics */
static int64_t g_inv_p1_mod_p2 = (-1);
static int64_t g_inv_p12_mod_p3 = (-1);
static __int128 g_P12 = 0;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t mod_inv_i64_i64(int64_t a, int64_t mod) {
return mod_pow_i64_i64_i64(a, (mod - 2), mod);
}
void ntt_ptr_i64_i64_i32_i64_i64(int64_t* a, int64_t n, int32_t invert, int64_t mod, int64_t root) {
int64_t j = 0;
int64_t i = 1;
while (i < n) {
int64_t bit = FLOW_CHECKED_SHR((n), (1));
while ((j & bit) != 0) {
j = (j ^ bit);
bit = FLOW_CHECKED_SHR((bit), (1));
}
j = (j ^ bit);
if (i < j) {
int64_t tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i = (i + 1);
}
int64_t length = 2;
while (length <= n) {
int64_t wlen = mod_pow_i64_i64_i64(root, FLOW_CHECKED_DIV(((mod - 1)), (length)), mod);
int64_t wl = wlen;
if (invert == 1) {
wl = mod_pow_i64_i64_i64(wlen, (mod - 2), mod);
}
int64_t half = FLOW_CHECKED_SHR((length), (1));
i = 0;
while (i < n) {
int64_t w = 1;
int64_t jj = 0;
while (jj < half) {
int64_t u = a[(i + jj)];
int64_t v = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a[((i + jj) + half)])) * ((__int128)(w)))), (((__int128)(mod))))));
int64_t x = (u + v);
if (x >= mod) {
x = (x - mod);
}
int64_t y = (u - v);
if (y < 0) {
y = (y + mod);
}
a[(i + jj)] = x;
a[((i + jj) + half)] = y;
w = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(w)) * ((__int128)(wl)))), (((__int128)(mod))))));
jj = (jj + 1);
}
i = (i + length);
}
length = FLOW_CHECKED_SHL((length), (1));
}
if (invert == 1) {
int64_t inv_n = mod_pow_i64_i64_i64(n, (mod - 2), mod);
i = 0;
while (i < n) {
a[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a[i])) * ((__int128)(inv_n)))), (((__int128)(mod))))));
i = (i + 1);
}
}
}
int64_t* convolve_one_ptr_i64_i64_ptr_i64_i64_i64_i64_ptr_i64(int64_t* a, int64_t n1, int64_t* b, int64_t n2, int64_t mod, int64_t root, int64_t* out_n) {
int64_t need = ((n1 + n2) - 1);
int64_t n = 1;
while (n < need) {
n = FLOW_CHECKED_SHL((n), (1));
}
int64_t* fa = (int64_t*)(((int64_t*)(calloc(n, 8))));
int64_t* fb = (int64_t*)(((int64_t*)(calloc(n, 8))));
int64_t i = 0;
while (i < n1) {
fa[i] = FLOW_CHECKED_MOD((a[i]), (mod));
i = (i + 1);
}
i = 0;
while (i < n2) {
fb[i] = FLOW_CHECKED_MOD((b[i]), (mod));
i = (i + 1);
}
ntt_ptr_i64_i64_i32_i64_i64(fa, n, 0, mod, root);
ntt_ptr_i64_i64_i32_i64_i64(fb, n, 0, mod, root);
i = 0;
while (i < n) {
fa[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fa[i])) * ((__int128)(fb[i])))), (((__int128)(mod))))));
i = (i + 1);
}
ntt_ptr_i64_i64_i32_i64_i64(fa, n, 1, mod, root);
out_n[0] = need;
int64_t* res = (int64_t*)(((int64_t*)(malloc((need * 8)))));
i = 0;
while (i < need) {
res[i] = fa[i];
i = (i + 1);
}
free(((void*)(fa)));
free(((void*)(fb)));
return res;
}
int64_t crt3_i64_i64_i64(int64_t a1, int64_t a2, int64_t a3) {
if (g_inv_p1_mod_p2 < 0) {
g_inv_p1_mod_p2 = mod_inv_i64_i64(FLOW_CHECKED_MOD((P1), (P2)), P2);
g_P12 = (((__int128)(P1)) * ((__int128)(P2)));
g_inv_p12_mod_p3 = mod_inv_i64_i64(((int64_t)(FLOW_CHECKED_MOD((g_P12), (((__int128)(P3)))))), P3);
}
int64_t t1 = FLOW_CHECKED_MOD(((a2 - a1)), (P2));
if (t1 < 0) {
t1 = (t1 + P2);
}
t1 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(t1)) * ((__int128)(g_inv_p1_mod_p2)))), (((__int128)(P2))))));
__int128 x2 = (((__int128)(a1)) + (((__int128)(P1)) * ((__int128)(t1))));
int64_t t2 = FLOW_CHECKED_MOD(((a3 - ((int64_t)(FLOW_CHECKED_MOD((x2), (((__int128)(P3)))))))), (P3));
if (t2 < 0) {
t2 = (t2 + P3);
}
t2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(t2)) * ((__int128)(g_inv_p12_mod_p3)))), (((__int128)(P3))))));
__int128 x = (x2 + (g_P12 * ((__int128)(t2))));
int64_t r = ((int64_t)(FLOW_CHECKED_MOD((x), (((__int128)(MOD))))));
if (r < 0) {
r = (r + MOD);
}
return r;
}
int64_t* convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(int64_t* a, int64_t n1, int64_t* b, int64_t n2, int64_t* out_n) {
if ((n1 == 0 || n2 == 0)) {
out_n[0] = 0;
return ((int64_t*)(NULL));
}
int64_t* o1p = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* o2p = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* o3p = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* c1 = (int64_t*)(convolve_one_ptr_i64_i64_ptr_i64_i64_i64_i64_ptr_i64(a, n1, b, n2, P1, 3, o1p));
int64_t* c2 = (int64_t*)(convolve_one_ptr_i64_i64_ptr_i64_i64_i64_i64_ptr_i64(a, n1, b, n2, P2, 3, o2p));
int64_t* c3 = (int64_t*)(convolve_one_ptr_i64_i64_ptr_i64_i64_i64_i64_ptr_i64(a, n1, b, n2, P3, 3, o3p));
int64_t need = ((n1 + n2) - 1);
int64_t* res = (int64_t*)(((int64_t*)(malloc((need * 8)))));
int64_t i = 0;
while (i < need) {
res[i] = crt3_i64_i64_i64(c1[i], c2[i], c3[i]);
i = (i + 1);
}
free(((void*)(c1)));
free(((void*)(c2)));
free(((void*)(c3)));
free(((void*)(o1p)));
free(((void*)(o2p)));
free(((void*)(o3p)));
out_n[0] = need;
return res;
}
int64_t* poly_mul_mod_ptr_i64_i64_ptr_i64_i64(int64_t* A, int64_t n, int64_t* B, int64_t m) {
if ((((n * m) <= 40000 || n < 40) || m < 40)) {
int64_t* res = (int64_t*)(((int64_t*)(calloc(((n + m) - 1), 8))));
int64_t i = 0;
while (i < n) {
if (A[i] != 0) {
int64_t j = 0;
while (j < m) {
res[(i + j)] = FLOW_CHECKED_MOD(((res[(i + j)] + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(A[i])) * ((__int128)(B[j])))), (((__int128)(MOD)))))))), (MOD));
j = (j + 1);
}
}
i = (i + 1);
}
return res;
}
int64_t* onp = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* r = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(A, n, B, m, onp));
free(((void*)(onp)));
return r;
}
int64_t* poly_inv_mod_ptr_i64_i64(int64_t* f, int64_t n) {
int64_t* g = (int64_t*)(((int64_t*)(calloc(n, 8))));
g[0] = mod_inv_i64_i64(f[0], MOD);
int64_t m = 1;
while (m < n) {
int64_t m2 = (m * 2);
int64_t m2c = m2;
if (m2c > n) {
m2c = n;
}
int64_t* fg = (int64_t*)(poly_mul_mod_ptr_i64_i64_ptr_i64_i64(f, m2c, g, m));
int64_t* h = (int64_t*)(((int64_t*)(calloc(m2c, 8))));
int64_t fglen = ((m2c + m) - 1);
int64_t i = 0;
while (i < m2c) {
int64_t v = ((i < fglen) ? (fg[i]) : (0));
h[i] = FLOW_CHECKED_MOD(((MOD - v)), (MOD));
i = (i + 1);
}
h[0] = FLOW_CHECKED_MOD(((h[0] + 2)), (MOD));
free(((void*)(fg)));
int64_t* ng = (int64_t*)(poly_mul_mod_ptr_i64_i64_ptr_i64_i64(g, m, h, m2c));
free(((void*)(g)));
free(((void*)(h)));
int64_t* gnew = (int64_t*)(((int64_t*)(calloc(m2c, 8))));
int64_t nglen = ((m + m2c) - 1);
i = 0;
while (i < m2c) {
gnew[i] = ((i < nglen) ? (ng[i]) : (0));
i = (i + 1);
}
free(((void*)(ng)));
g = gnew;
m = m2c;
}
return g;
}
void pre_fac_pow_i64_i64_ptr_i64_ptr_i64(int64_t n, int64_t r, int64_t* fac_pow, int64_t* inv_fac_pow) {
fac_pow[0] = 1;
int64_t i = 1;
while (i <= n) {
int64_t ip = mod_pow_i64_i64_i64(i, r, MOD);
fac_pow[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fac_pow[(i - 1)])) * ((__int128)(ip)))), (((__int128)(MOD))))));
i = (i + 1);
}
inv_fac_pow[n] = mod_inv_i64_i64(fac_pow[n], MOD);
i = (n - 1);
while (i >= 0) {
int64_t ip = mod_pow_i64_i64_i64((i + 1), r, MOD);
inv_fac_pow[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(inv_fac_pow[(i + 1)])) * ((__int128)(ip)))), (((__int128)(MOD))))));
i = (i - 1);
}
}
int64_t P_via_dp_i64_i64_ptr_i64_ptr_i64(int64_t k, int64_t n, int64_t* fac_pow, int64_t* inv_fac_pow) {
int64_t q = FLOW_CHECKED_DIV((n), (k));
int64_t rem = FLOW_CHECKED_MOD((n), (k));
int64_t m = (q + ((rem != 0) ? (1) : (0)));
int64_t* blocks = (int64_t*)(((int64_t*)(malloc((m * 8)))));
int64_t i = 0;
while (i < q) {
blocks[i] = k;
i = (i + 1);
}
if (rem != 0) {
blocks[q] = rem;
}
int64_t* f = (int64_t*)(((int64_t*)(calloc((m + 1), 8))));
f[0] = fac_pow[n];
i = 1;
while (i <= m) {
int64_t seg = 0;
int64_t acc = 0;
int64_t j = (i - 1);
while (j >= 0) {
seg = (seg + blocks[j]);
int64_t term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(f[j])) * ((__int128)(inv_fac_pow[seg])))), (((__int128)(MOD))))));
if (FLOW_CHECKED_MOD(((i - j)), (2)) == 1) {
acc = (acc + term);
} else {
acc = (acc - term);
}
j = (j - 1);
}
acc = FLOW_CHECKED_MOD((acc), (MOD));
if (acc < 0) {
acc = (acc + MOD);
}
f[i] = acc;
i = (i + 1);
}
int64_t ans = f[m];
free(((void*)(blocks)));
free(((void*)(f)));
return ans;
}
int64_t P_via_inverse_i64_i64_ptr_i64_ptr_i64(int64_t k, int64_t n, int64_t* fac_pow, int64_t* inv_fac_pow) {
int64_t q = FLOW_CHECKED_DIV((n), (k));
int64_t rem = FLOW_CHECKED_MOD((n), (k));
int64_t* p = (int64_t*)(((int64_t*)(calloc((q + 1), 8))));
p[0] = 1;
int64_t d = 1;
while (d <= q) {
int64_t coeff = inv_fac_pow[(d * k)];
if (FLOW_CHECKED_MOD((d), (2)) == 1) {
coeff = FLOW_CHECKED_MOD(((MOD - coeff)), (MOD));
}
p[d] = coeff;
d = (d + 1);
}
int64_t* s = (int64_t*)(poly_inv_mod_ptr_i64_i64(p, (q + 1)));
int64_t g0 = fac_pow[n];
int64_t* g = (int64_t*)(((int64_t*)(malloc(((q + 1) * 8)))));
int64_t i = 0;
while (i <= q) {
g[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g0)) * ((__int128)(s[i])))), (((__int128)(MOD))))));
i = (i + 1);
}
if (rem == 0) {
int64_t a2 = g[q];
free(((void*)(p)));
free(((void*)(s)));
free(((void*)(g)));
return a2;
}
int64_t ans = 0;
i = 0;
while (i <= q) {
int64_t seg_len = (((q - i) * k) + rem);
int64_t term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(g[i])) * ((__int128)(inv_fac_pow[seg_len])))), (((__int128)(MOD))))));
if (FLOW_CHECKED_MOD(((q - i)), (2)) == 1) {
ans = (ans - term);
} else {
ans = (ans + term);
}
i = (i + 1);
}
int64_t a3 = FLOW_CHECKED_MOD((ans), (MOD));
if (a3 < 0) {
a3 = (a3 + MOD);
}
free(((void*)(p)));
free(((void*)(s)));
free(((void*)(g)));
return a3;
}
int64_t Qn_i64(int64_t n) {
int64_t r = n;
int64_t* fac_pow = (int64_t*)(((int64_t*)(malloc(((n + 1) * 8)))));
int64_t* inv_fac_pow = (int64_t*)(((int64_t*)(malloc(((n + 1) * 8)))));
pre_fac_pow_i64_i64_ptr_i64_ptr_i64(n, r, fac_pow, inv_fac_pow);
int64_t k_inv_max = FLOW_CHECKED_DIV((n), (200));
int64_t ans = 0;
int64_t k = 1;
while (k <= n) {
int64_t q = FLOW_CHECKED_DIV((n), (k));
int64_t v = 0;
if ((k <= k_inv_max && q > 200)) {
v = P_via_inverse_i64_i64_ptr_i64_ptr_i64(k, n, fac_pow, inv_fac_pow);
} else {
v = P_via_dp_i64_i64_ptr_i64_ptr_i64(k, n, fac_pow, inv_fac_pow);
}
ans = (ans + v);
if (ans >= MOD) {
ans = (ans - MOD);
}
k = (k + 1);
}
free(((void*)(fac_pow)));
free(((void*)(inv_fac_pow)));
return ans;
}
int32_t main(void) {
printf("%lld\n", Qn_i64(50000));
return 0;
}