# Project Euler 553
# Power Sets of Power Sets — EGF log/exp via NTT.
# Ported from C to pure Flow. MOD = 10^9+7.
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 = 1000000007
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_hi: i64 = 0
let mut g_P12_lo: i64 = 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)
let p12: i128 = (P1 as i128) * (P2 as i128)
g_P12_lo = (p12 & ((1 as i128) << 63) - 1) as i64
g_P12_hi = (p12 >> 63) as i64
g_inv_p12_mod_p3 = mod_inv((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 p12: i128 = ((g_P12_hi as i128) << 63) + (g_P12_lo as i128)
let x: i128 = x2 + 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_inv(f: ptr<i64>, deg: i64) -> ptr<i64> {
let mut g: ptr<i64> = calloc(deg, 8) as ptr<i64>
g[0] = mod_inv(f[0], MOD)
let mut m: i64 = 1
while m < deg {
let m2: i64 = m * 2
let mut m2c: i64 = m2
if m2c > deg { m2c = deg }
let onp: ptr<i64> = calloc(1, 8) as ptr<i64>
let fg: ptr<i64> = convolve_mod(f, m2c, g, m, onp)
let on: i64 = onp[0]
if on > m2c { on = m2c }
free(onp as ptr<void>)
let h: ptr<i64> = calloc(m2c, 8) as ptr<i64>
let mut i: i64 = 0
while i < on && i < m2c {
h[i] = (MOD - fg[i]) % MOD
i = i + 1
}
h[0] = (h[0] + 2) % MOD
free(fg as ptr<void>)
let onp2: ptr<i64> = calloc(1, 8) as ptr<i64>
let ng: ptr<i64> = convolve_mod(g, m, h, m2c, onp2)
free(onp2 as ptr<void>)
free(g as ptr<void>)
free(h as ptr<void>)
let gnew: ptr<i64> = calloc(m2c, 8) as ptr<i64>
i = 0
while i < m2c { gnew[i] = ng[i]; i = i + 1 }
free(ng as ptr<void>)
g = gnew
m = m2c
}
return g
}
function poly_log(f: ptr<i64>, deg: i64, inv_int: ptr<i64>) -> ptr<i64> {
let df: ptr<i64> = malloc((deg - 1) * 8) as ptr<i64>
let mut i: i64 = 1
while i < deg {
df[i - 1] = ((i as i128) * (f[i] as i128) % (MOD as i128)) as i64
i = i + 1
}
let invf: ptr<i64> = poly_inv(f, deg)
let onp: ptr<i64> = calloc(1, 8) as ptr<i64>
let prod: ptr<i64> = convolve_mod(df, deg - 1, invf, deg, onp)
let on: i64 = onp[0]
free(onp as ptr<void>)
let res: ptr<i64> = calloc(deg, 8) as ptr<i64>
i = 1
while i < deg {
if i - 1 < on {
res[i] = ((prod[i - 1] as i128) * (inv_int[i] as i128) % (MOD as i128)) as i64
}
i = i + 1
}
free(df as ptr<void>)
free(invf as ptr<void>)
free(prod as ptr<void>)
return res
}
function poly_pow(a: ptr<i64>, deg: i64, exp0: i64) -> ptr<i64> {
let mut res: ptr<i64> = calloc(deg, 8) as ptr<i64>
res[0] = 1
let mut base: ptr<i64> = malloc(deg * 8) as ptr<i64>
let mut i: i64 = 0
while i < deg { base[i] = a[i]; i = i + 1 }
let mut e: i64 = exp0
while e > 0 {
if e % 2 == 1 {
let onp: ptr<i64> = calloc(1, 8) as ptr<i64>
let tmp: ptr<i64> = convolve_mod(res, deg, base, deg, onp)
let on: i64 = onp[0]
free(onp as ptr<void>)
i = 0
while i < deg { res[i] = 0; i = i + 1 }
i = 0
while i < deg && i < on { res[i] = tmp[i]; i = i + 1 }
free(tmp as ptr<void>)
}
e = e / 2
if e > 0 {
let onp2: ptr<i64> = calloc(1, 8) as ptr<i64>
let tmp2: ptr<i64> = convolve_mod(base, deg, base, deg, onp2)
let on2: i64 = onp2[0]
free(onp2 as ptr<void>)
i = 0
while i < deg { base[i] = 0; i = i + 1 }
i = 0
while i < deg && i < on2 { base[i] = tmp2[i]; i = i + 1 }
free(tmp2 as ptr<void>)
}
}
free(base as ptr<void>)
return res
}
function precompute(n: i64, fact: ptr<i64>, inv_fact: ptr<i64>, inv_int: ptr<i64>) -> void {
fact[0] = 1
let mut i: i64 = 1
while i <= n {
fact[i] = ((fact[i - 1] as i128) * (i as i128) % (MOD as i128)) as i64
i = i + 1
}
inv_fact[n] = mod_inv(fact[n], MOD)
i = n
while i > 0 {
inv_fact[i - 1] = ((inv_fact[i] as i128) * (i as i128) % (MOD as i128)) as i64
i = i - 1
}
inv_int[0] = 0
if n >= 1 { inv_int[1] = 1 }
i = 2
while i <= n {
inv_int[i] = MOD - ((MOD / i) as i128 * (inv_int[MOD % i] as i128) % (MOD as i128)) as i64
i = i + 1
}
}
function compute_A(max_n: i64, inv_fact: ptr<i64>, inv_int: ptr<i64>) -> ptr<i64> {
let modm1: i64 = MOD - 1
let exp2: ptr<i64> = malloc((max_n + 1) * 8) as ptr<i64>
exp2[0] = 1
let mut i: i64 = 1
while i <= max_n {
exp2[i] = (exp2[i - 1] * 2) % modm1
i = i + 1
}
let A0: ptr<i64> = malloc((max_n + 1) * 8) as ptr<i64>
i = 0
while i <= max_n {
A0[i] = mod_pow(2, (exp2[i] - 1) % modm1, MOD)
i = i + 1
}
let p: ptr<i64> = malloc((max_n + 1) * 8) as ptr<i64>
let q: ptr<i64> = malloc((max_n + 1) * 8) as ptr<i64>
i = 0
while i <= max_n {
p[i] = ((A0[i] as i128) * (inv_fact[i] as i128) % (MOD as i128)) as i64
if i % 2 == 1 {
q[i] = (MOD - inv_fact[i]) % MOD
} else {
q[i] = inv_fact[i]
}
i = i + 1
}
let onp: ptr<i64> = calloc(1, 8) as ptr<i64>
let H: ptr<i64> = convolve_mod(p, max_n + 1, q, max_n + 1, onp)
let on: i64 = onp[0]
free(onp as ptr<void>)
let H2: ptr<i64> = calloc((max_n + 1), 8) as ptr<i64>
i = 0
while i <= max_n && i < on { H2[i] = H[i]; i = i + 1 }
H2[0] = 1
free(H as ptr<void>)
let A: ptr<i64> = poly_log(H2, max_n + 1, inv_int)
free(exp2 as ptr<void>)
free(A0 as ptr<void>)
free(p as ptr<void>)
free(q as ptr<void>)
free(H2 as ptr<void>)
return A
}
function C_nk(n: i64, k: i64, A_series: ptr<i64>, fact: ptr<i64>, inv_fact: ptr<i64>) -> i64 {
let deg: i64 = n + 1
let Ak: ptr<i64> = poly_pow(A_series, deg, k)
let onp: ptr<i64> = calloc(1, 8) as ptr<i64>
let prod: ptr<i64> = convolve_mod(Ak, deg, inv_fact, deg, onp)
let on: i64 = onp[0]
free(onp as ptr<void>)
let pn: i64 = if n < on { prod[n] } else { 0 }
let ans: i64 = ((fact[n] as i128) * (pn as i128) % (MOD as i128) * (inv_fact[k] as i128) % (MOD as i128)) as i64
free(Ak as ptr<void>)
free(prod as ptr<void>)
return ans
}
function main() -> i32 {
let N: i64 = 10000
let K: i64 = 10
let fact: ptr<i64> = malloc((N + 1) * 8) as ptr<i64>
let inv_fact: ptr<i64> = malloc((N + 1) * 8) as ptr<i64>
let inv_int: ptr<i64> = malloc((N + 1) * 8) as ptr<i64>
precompute(N, fact, inv_fact, inv_int)
let A: ptr<i64> = compute_A(N, inv_fact, inv_int)
let ans: i64 = C_nk(N, K, A, fact, inv_fact)
free(fact as ptr<void>)
free(inv_fact as ptr<void>)
free(inv_int as ptr<void>)
free(A as ptr<void>)
printf("%lld\n", ans)
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_inv_ptr_i64_i64(int64_t* f, int64_t deg);
int64_t* poly_log_ptr_i64_i64_ptr_i64(int64_t* f, int64_t deg, int64_t* inv_int);
int64_t* poly_pow_ptr_i64_i64_i64(int64_t* a, int64_t deg, int64_t exp0);
void precompute_i64_ptr_i64_ptr_i64_ptr_i64(int64_t n, int64_t* fact, int64_t* inv_fact, int64_t* inv_int);
int64_t* compute_A_i64_ptr_i64_ptr_i64(int64_t max_n, int64_t* inv_fact, int64_t* inv_int);
int64_t C_nk_i64_i64_ptr_i64_ptr_i64_ptr_i64(int64_t n, int64_t k, int64_t* A_series, int64_t* fact, int64_t* inv_fact);
int32_t main(void);
static const int64_t MOD = 1000000007;
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 int64_t g_P12_hi = 0;
static int64_t g_P12_lo = 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);
__int128 p12 = (((__int128)(P1)) * ((__int128)(P2)));
g_P12_lo = ((int64_t)((p12 & (FLOW_CHECKED_SHL((((__int128)(1))), (63)) - 1))));
g_P12_hi = ((int64_t)(FLOW_CHECKED_SHR((p12), (63))));
g_inv_p12_mod_p3 = mod_inv_i64_i64(((int64_t)(FLOW_CHECKED_MOD((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 p12 = (FLOW_CHECKED_SHL((((__int128)(g_P12_hi))), (63)) + ((__int128)(g_P12_lo)));
__int128 x = (x2 + (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_inv_ptr_i64_i64(int64_t* f, int64_t deg) {
int64_t* g = (int64_t*)(((int64_t*)(calloc(deg, 8))));
g[0] = mod_inv_i64_i64(f[0], MOD);
int64_t m = 1;
while (m < deg) {
int64_t m2 = (m * 2);
int64_t m2c = m2;
if (m2c > deg) {
m2c = deg;
}
int64_t* onp = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* fg = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(f, m2c, g, m, onp));
int64_t on = onp[0];
if (on > m2c) {
on = m2c;
}
free(((void*)(onp)));
int64_t* h = (int64_t*)(((int64_t*)(calloc(m2c, 8))));
int64_t i = 0;
while ((i < on && i < m2c)) {
h[i] = FLOW_CHECKED_MOD(((MOD - fg[i])), (MOD));
i = (i + 1);
}
h[0] = FLOW_CHECKED_MOD(((h[0] + 2)), (MOD));
free(((void*)(fg)));
int64_t* onp2 = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* ng = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(g, m, h, m2c, onp2));
free(((void*)(onp2)));
free(((void*)(g)));
free(((void*)(h)));
int64_t* gnew = (int64_t*)(((int64_t*)(calloc(m2c, 8))));
i = 0;
while (i < m2c) {
gnew[i] = ng[i];
i = (i + 1);
}
free(((void*)(ng)));
g = gnew;
m = m2c;
}
return g;
}
int64_t* poly_log_ptr_i64_i64_ptr_i64(int64_t* f, int64_t deg, int64_t* inv_int) {
int64_t* df = (int64_t*)(((int64_t*)(malloc(((deg - 1) * 8)))));
int64_t i = 1;
while (i < deg) {
df[(i - 1)] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(i)) * ((__int128)(f[i])))), (((__int128)(MOD))))));
i = (i + 1);
}
int64_t* invf = (int64_t*)(poly_inv_ptr_i64_i64(f, deg));
int64_t* onp = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* prod = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(df, (deg - 1), invf, deg, onp));
int64_t on = onp[0];
free(((void*)(onp)));
int64_t* res = (int64_t*)(((int64_t*)(calloc(deg, 8))));
i = 1;
while (i < deg) {
if ((i - 1) < on) {
res[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(prod[(i - 1)])) * ((__int128)(inv_int[i])))), (((__int128)(MOD))))));
}
i = (i + 1);
}
free(((void*)(df)));
free(((void*)(invf)));
free(((void*)(prod)));
return res;
}
int64_t* poly_pow_ptr_i64_i64_i64(int64_t* a, int64_t deg, int64_t exp0) {
int64_t* res = (int64_t*)(((int64_t*)(calloc(deg, 8))));
res[0] = 1;
int64_t* base = (int64_t*)(((int64_t*)(malloc((deg * 8)))));
int64_t i = 0;
while (i < deg) {
base[i] = a[i];
i = (i + 1);
}
int64_t e = exp0;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
int64_t* onp = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* tmp = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(res, deg, base, deg, onp));
int64_t on = onp[0];
free(((void*)(onp)));
i = 0;
while (i < deg) {
res[i] = 0;
i = (i + 1);
}
i = 0;
while ((i < deg && i < on)) {
res[i] = tmp[i];
i = (i + 1);
}
free(((void*)(tmp)));
}
e = FLOW_CHECKED_DIV((e), (2));
if (e > 0) {
int64_t* onp2 = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* tmp2 = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(base, deg, base, deg, onp2));
int64_t on2 = onp2[0];
free(((void*)(onp2)));
i = 0;
while (i < deg) {
base[i] = 0;
i = (i + 1);
}
i = 0;
while ((i < deg && i < on2)) {
base[i] = tmp2[i];
i = (i + 1);
}
free(((void*)(tmp2)));
}
}
free(((void*)(base)));
return res;
}
void precompute_i64_ptr_i64_ptr_i64_ptr_i64(int64_t n, int64_t* fact, int64_t* inv_fact, int64_t* inv_int) {
fact[0] = 1;
int64_t i = 1;
while (i <= n) {
fact[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(fact[(i - 1)])) * ((__int128)(i)))), (((__int128)(MOD))))));
i = (i + 1);
}
inv_fact[n] = mod_inv_i64_i64(fact[n], MOD);
i = n;
while (i > 0) {
inv_fact[(i - 1)] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(inv_fact[i])) * ((__int128)(i)))), (((__int128)(MOD))))));
i = (i - 1);
}
inv_int[0] = 0;
if (n >= 1) {
inv_int[1] = 1;
}
i = 2;
while (i <= n) {
inv_int[i] = (MOD - ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_DIV((MOD), (i)))) * ((__int128)(inv_int[FLOW_CHECKED_MOD((MOD), (i))])))), (((__int128)(MOD)))))));
i = (i + 1);
}
}
int64_t* compute_A_i64_ptr_i64_ptr_i64(int64_t max_n, int64_t* inv_fact, int64_t* inv_int) {
int64_t modm1 = (MOD - 1);
int64_t* exp2 = (int64_t*)(((int64_t*)(malloc(((max_n + 1) * 8)))));
exp2[0] = 1;
int64_t i = 1;
while (i <= max_n) {
exp2[i] = FLOW_CHECKED_MOD(((exp2[(i - 1)] * 2)), (modm1));
i = (i + 1);
}
int64_t* A0 = (int64_t*)(((int64_t*)(malloc(((max_n + 1) * 8)))));
i = 0;
while (i <= max_n) {
A0[i] = mod_pow_i64_i64_i64(2, FLOW_CHECKED_MOD(((exp2[i] - 1)), (modm1)), MOD);
i = (i + 1);
}
int64_t* p = (int64_t*)(((int64_t*)(malloc(((max_n + 1) * 8)))));
int64_t* q = (int64_t*)(((int64_t*)(malloc(((max_n + 1) * 8)))));
i = 0;
while (i <= max_n) {
p[i] = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(A0[i])) * ((__int128)(inv_fact[i])))), (((__int128)(MOD))))));
if (FLOW_CHECKED_MOD((i), (2)) == 1) {
q[i] = FLOW_CHECKED_MOD(((MOD - inv_fact[i])), (MOD));
} else {
q[i] = inv_fact[i];
}
i = (i + 1);
}
int64_t* onp = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* H = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(p, (max_n + 1), q, (max_n + 1), onp));
int64_t on = onp[0];
free(((void*)(onp)));
int64_t* H2 = (int64_t*)(((int64_t*)(calloc((max_n + 1), 8))));
i = 0;
while ((i <= max_n && i < on)) {
H2[i] = H[i];
i = (i + 1);
}
H2[0] = 1;
free(((void*)(H)));
int64_t* A = (int64_t*)(poly_log_ptr_i64_i64_ptr_i64(H2, (max_n + 1), inv_int));
free(((void*)(exp2)));
free(((void*)(A0)));
free(((void*)(p)));
free(((void*)(q)));
free(((void*)(H2)));
return A;
}
int64_t C_nk_i64_i64_ptr_i64_ptr_i64_ptr_i64(int64_t n, int64_t k, int64_t* A_series, int64_t* fact, int64_t* inv_fact) {
int64_t deg = (n + 1);
int64_t* Ak = (int64_t*)(poly_pow_ptr_i64_i64_i64(A_series, deg, k));
int64_t* onp = (int64_t*)(((int64_t*)(calloc(1, 8))));
int64_t* prod = (int64_t*)(convolve_mod_ptr_i64_i64_ptr_i64_i64_ptr_i64(Ak, deg, inv_fact, deg, onp));
int64_t on = onp[0];
free(((void*)(onp)));
int64_t pn = ((n < on) ? (prod[n]) : (0));
int64_t ans = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((((__int128)(fact[n])) * ((__int128)(pn)))), (((__int128)(MOD)))) * ((__int128)(inv_fact[k])))), (((__int128)(MOD))))));
free(((void*)(Ak)));
free(((void*)(prod)));
return ans;
}
int32_t main(void) {
int64_t N = 10000;
int64_t K = 10;
int64_t* fact = (int64_t*)(((int64_t*)(malloc(((N + 1) * 8)))));
int64_t* inv_fact = (int64_t*)(((int64_t*)(malloc(((N + 1) * 8)))));
int64_t* inv_int = (int64_t*)(((int64_t*)(malloc(((N + 1) * 8)))));
precompute_i64_ptr_i64_ptr_i64_ptr_i64(N, fact, inv_fact, inv_int);
int64_t* A = (int64_t*)(compute_A_i64_ptr_i64_ptr_i64(N, inv_fact, inv_int));
int64_t ans = C_nk_i64_i64_ptr_i64_ptr_i64_ptr_i64(N, K, A, fact, inv_fact);
free(((void*)(fact)));
free(((void*)(inv_fact)));
free(((void*)(inv_int)));
free(((void*)(A)));
printf("%lld\n", ans);
return 0;
}