# Project Euler 842
# Irregular Star Polygons - sum T(n) mod 1e9+7 for n=3..60.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(p: ptr<void>, c: i32, n: i64) -> ptr<void>
function cos(x: f64) -> f64
function sin(x: f64) -> f64
function fabs(x: f64) -> f64
function floor(x: f64) -> f64
function llround(x: f64) -> i64
}
const MOD: i64 = 1000000007
const SCALE: i64 = 100000000000
const HASH_SIZE: i64 = 1048576
const HASH_MASK: i64 = 1048575
const MAX_POINTS: i64 = 600000
const MAX_REPS: i64 = 600000
let mut fact_mod: ptr<i64> = null
let mut inv_fact_mod: ptr<i64> = null
let mut pts_qx: ptr<i64> = null
let mut pts_qy: ptr<i64> = null
let mut pts_count: ptr<i32> = null
let mut num_points: i64 = 0
let mut hash_buckets: ptr<i32> = null
let mut hash_next: ptr<i32> = null
let mut reps_x: ptr<f64> = null
let mut reps_y: ptr<f64> = null
let mut reps_cnt: ptr<i32> = null
let mut num_reps: i64 = 0
let mut grid_buckets: ptr<i32> = null
let mut grid_next: ptr<i32> = null
function modpow(b0: i64, e0: i64, m0: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = b0 % m0
let mut e: i64 = e0
while e > 0 {
if (e & 1) != 0 {
r = ((r as i128) * (b as i128) % (m0 as i128)) as i64
}
b = ((b as i128) * (b as i128) % (m0 as i128)) as i64
e = e >> 1
}
return r
}
function modinv(a: i64, m: i64) -> i64 {
return modpow(a, m - 2, m)
}
function init_factorials() -> void {
fact_mod = calloc(61, 8)
inv_fact_mod = calloc(61, 8)
fact_mod[0] = 1
let mut i: i64 = 1
while i <= 60 {
fact_mod[i] = (fact_mod[i - 1] * i) % MOD
i = i + 1
}
i = 0
while i <= 60 {
inv_fact_mod[i] = modinv(fact_mod[i], MOD)
i = i + 1
}
}
function comb_mod(n: i64, k: i64) -> i64 {
if k < 0 || k > n {
return 0
}
return (fact_mod[n] * inv_fact_mod[k] % MOD * inv_fact_mod[n - k] % MOD) as i64
}
function cycles_at_least_two_edges(n: i64, m: i64) -> i64 {
if m < 2 {
return 0
}
let inv2: i64 = modinv(2, MOD)
let total: i64 = fact_mod[n - 1] * inv2 % MOD
let mut c0: i64 = 0
let mut k: i64 = 0
while k <= m {
let ak: i64 = 0
if k == 0 {
ak = total
} else {
ak = modpow(2, k - 1, MOD) * fact_mod[n - k - 1] % MOD
}
let term: i64 = comb_mod(m, k) * ak % MOD
if k % 2 == 0 {
c0 = (c0 + term) % MOD
} else {
c0 = (c0 - term % MOD + MOD) % MOD
}
k = k + 1
}
let mut c1: i64 = 0
k = 1
while k <= m {
let ak: i64 = modpow(2, k - 1, MOD) * fact_mod[n - k - 1] % MOD
let term: i64 = (k * comb_mod(m, k) % MOD) * ak % MOD
if (k - 1) % 2 == 0 {
c1 = (c1 + term) % MOD
} else {
c1 = (c1 - term % MOD + MOD) % MOD
}
k = k + 1
}
return (total - c0 - c1 % MOD + 2 * MOD) % MOD
}
function isqrt_ll(n: i64) -> i64 {
if n < 0 {
return -1
}
if n == 0 {
return 0
}
let mut x: i64 = 0
# Newton's method
let mut bit: i64 = 1
while bit <= n {
bit = bit << 2
}
bit = bit >> 2
while bit != 0 {
if n >= x + bit {
n = n - (x + bit)
x = (x >> 1) + bit
} else {
x = x >> 1
}
bit = bit >> 2
}
return x
}
function inv_triangular(q: i64) -> i64 {
let disc: i64 = 1 + 8 * q
let r: i64 = isqrt_ll(disc)
if r * r != disc {
return -1
}
if (1 + r) % 2 != 0 {
return -1
}
return (1 + r) / 2
}
function hash_key(qx: i64, qy: i64) -> i64 {
let h: i64 = qx * 1000000007 + qy
# mix high bits down
let hi: i64 = (h as i64) >> 32
let lo: i64 = h & 0xFFFFFFFF
let mixed: i64 = (lo ^ hi) & HASH_MASK
return mixed
}
function find_point(qx: i64, qy: i64) -> i64 {
let h: i64 = hash_key(qx, qy)
let mut idx: i64 = hash_buckets[h] as i64
while idx != -1 {
if pts_qx[idx] == qx && pts_qy[idx] == qy {
return idx
}
idx = hash_next[idx] as i64
}
return -1
}
function add_point_fast(qx: i64, qy: i64) -> void {
let idx: i64 = find_point(qx, qy)
if idx >= 0 {
pts_count[idx] = pts_count[idx] + 1
return
}
idx = num_points
num_points = num_points + 1
pts_qx[idx] = qx
pts_qy[idx] = qy
pts_count[idx] = 1
let h: i64 = hash_key(qx, qy)
hash_next[idx] = hash_buckets[h]
hash_buckets[h] = idx as i32
}
function grid_key(x: f64, y: f64) -> i64 {
let ix: i64 = floor(x / 0.000001) as i64
let iy: i64 = floor(y / 0.000001) as i64
let h: i64 = ix * 1000000007 + iy
let hi: i64 = (h as i64) >> 32
let lo: i64 = h & 0xFFFFFFFF
return (lo ^ hi) & HASH_MASK
}
function add_point_slow(x: f64, y: f64) -> void {
let ix: i64 = floor(x / 0.000001) as i64
let iy: i64 = floor(y / 0.000001) as i64
let mut dx: i64 = -1
while dx <= 1 {
let mut dy: i64 = -1
while dy <= 1 {
let cx: i64 = ix + dx
let cy: i64 = iy + dy
let h2: i64 = cx * 1000000007 + cy
let hi: i64 = (h2 as i64) >> 32
let lo: i64 = h2 & 0xFFFFFFFF
let h: i64 = (lo ^ hi) & HASH_MASK
let mut idx: i64 = grid_buckets[h] as i64
while idx != -1 {
let ddx: f64 = x - reps_x[idx]
let ddy: f64 = y - reps_y[idx]
if ddx * ddx + ddy * ddy <= 1e-18 {
reps_cnt[idx] = reps_cnt[idx] + 1
return
}
idx = grid_next[idx] as i64
}
dy = dy + 1
}
dx = dx + 1
}
let idx: i64 = num_reps
num_reps = num_reps + 1
reps_x[idx] = x
reps_y[idx] = y
reps_cnt[idx] = 1
let h: i64 = grid_key(x, y)
grid_next[idx] = grid_buckets[h]
grid_buckets[h] = idx as i32
}
function compute_points_fast(n: i64, xs: ptr<f64>, ys: ptr<f64>) -> i32 {
num_points = 0
let mut i: i64 = 0
while i < HASH_SIZE {
hash_buckets[i] = -1
i = i + 1
}
let mut a: i64 = 0
while a < n - 3 {
let x1: f64 = xs[a]
let y1: f64 = ys[a]
let mut b: i64 = a + 1
while b < n - 2 {
let x3: f64 = xs[b]
let y3: f64 = ys[b]
let abx: f64 = x3 - x1
let aby: f64 = y3 - y1
let mut c: i64 = b + 1
while c < n - 1 {
let x2: f64 = xs[c]
let y2: f64 = ys[c]
let dx12: f64 = x2 - x1
let dy12: f64 = y2 - y1
let mut d: i64 = c + 1
while d < n {
let x4: f64 = xs[d]
let y4: f64 = ys[d]
let dx34: f64 = x4 - x3
let dy34: f64 = y4 - y3
let denom: f64 = dx12 * dy34 - dy12 * dx34
if fabs(denom) < 1e-18 {
d = d + 1
continue
}
let t: f64 = (abx * dy34 - aby * dx34) / denom
let px: f64 = x1 + t * dx12
let py: f64 = y1 + t * dy12
let qx: i64 = llround(px * (SCALE as f64))
let qy: i64 = llround(py * (SCALE as f64))
add_point_fast(qx, qy)
d = d + 1
}
c = c + 1
}
b = b + 1
}
a = a + 1
}
i = 0
while i < num_points {
if inv_triangular(pts_count[i] as i64) < 0 {
return 0
}
i = i + 1
}
return 1
}
function compute_points_slow(n: i64, xs: ptr<f64>, ys: ptr<f64>) -> void {
num_reps = 0
let mut i: i64 = 0
while i < HASH_SIZE {
grid_buckets[i] = -1
i = i + 1
}
let mut a: i64 = 0
while a < n - 3 {
let x1: f64 = xs[a]
let y1: f64 = ys[a]
let mut b: i64 = a + 1
while b < n - 2 {
let x3: f64 = xs[b]
let y3: f64 = ys[b]
let abx: f64 = x3 - x1
let aby: f64 = y3 - y1
let mut c: i64 = b + 1
while c < n - 1 {
let x2: f64 = xs[c]
let y2: f64 = ys[c]
let dx12: f64 = x2 - x1
let dy12: f64 = y2 - y1
let mut d: i64 = c + 1
while d < n {
let x4: f64 = xs[d]
let y4: f64 = ys[d]
let dx34: f64 = x4 - x3
let dy34: f64 = y4 - y3
let denom: f64 = dx12 * dy34 - dy12 * dx34
if fabs(denom) < 1e-18 {
d = d + 1
continue
}
let t: f64 = (abx * dy34 - aby * dx34) / denom
let px: f64 = x1 + t * dx12
let py: f64 = y1 + t * dy12
add_point_slow(px, py)
d = d + 1
}
c = c + 1
}
b = b + 1
}
a = a + 1
}
}
function T_mod(n: i64) -> i64 {
if n < 4 {
return 0
}
let tau: f64 = 2.0 * 3.14159265358979323846
let xs: ptr<f64> = calloc(60, 8)
let ys: ptr<f64> = calloc(60, 8)
let mut k: i64 = 0
while k < n {
xs[k] = cos(tau * (k as f64) / (n as f64))
ys[k] = sin(tau * (k as f64) / (n as f64))
k = k + 1
}
let dist_m: ptr<i64> = calloc(100, 8)
let dist_cnt: ptr<i64> = calloc(100, 8)
let mut dist_size: i64 = 0
let fast: i32 = compute_points_fast(n, xs, ys)
if fast != 0 {
let mut i: i64 = 0
while i < num_points {
let m: i64 = inv_triangular(pts_count[i] as i64)
let mut found: i64 = -1
let mut j: i64 = 0
while j < dist_size {
if dist_m[j] == m {
found = j
break
}
j = j + 1
}
if found < 0 {
dist_m[dist_size] = m
dist_cnt[dist_size] = 1
dist_size = dist_size + 1
} else {
dist_cnt[found] = dist_cnt[found] + 1
}
i = i + 1
}
} else {
compute_points_slow(n, xs, ys)
let mut i: i64 = 0
while i < num_reps {
let m: i64 = inv_triangular(reps_cnt[i] as i64)
if m < 0 {
i = i + 1
continue
}
let mut found: i64 = -1
let mut j: i64 = 0
while j < dist_size {
if dist_m[j] == m {
found = j
break
}
j = j + 1
}
if found < 0 {
dist_m[dist_size] = m
dist_cnt[dist_size] = 1
dist_size = dist_size + 1
} else {
dist_cnt[found] = dist_cnt[found] + 1
}
i = i + 1
}
}
let mut total: i64 = 0
let mut i: i64 = 0
while i < dist_size {
let g: i64 = cycles_at_least_two_edges(n, dist_m[i])
total = (total + dist_cnt[i] * g) % MOD
i = i + 1
}
free(xs)
free(ys)
free(dist_m)
free(dist_cnt)
return total
}
function main() -> i32 {
init_factorials()
pts_qx = calloc(MAX_POINTS, 8)
pts_qy = calloc(MAX_POINTS, 8)
pts_count = calloc(MAX_POINTS, 4)
hash_buckets = calloc(HASH_SIZE, 4)
hash_next = calloc(MAX_POINTS, 4)
reps_x = calloc(MAX_REPS, 8)
reps_y = calloc(MAX_REPS, 8)
reps_cnt = calloc(MAX_REPS, 4)
grid_buckets = calloc(HASH_SIZE, 4)
grid_next = calloc(MAX_REPS, 4)
let mut ans: i64 = 0
let mut n: i64 = 3
while n <= 60 {
ans = (ans + T_mod(n)) % MOD
n = n + 1
}
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 llround(double x);
int64_t modpow_i64_i64_i64(int64_t b0, int64_t e0, int64_t m0);
int64_t modinv_i64_i64(int64_t a, int64_t m);
void init_factorials(void);
int64_t comb_mod_i64_i64(int64_t n, int64_t k);
int64_t cycles_at_least_two_edges_i64_i64(int64_t n, int64_t m);
int64_t isqrt_ll_i64(int64_t n);
int64_t inv_triangular_i64(int64_t q);
int64_t hash_key_i64_i64(int64_t qx, int64_t qy);
int64_t find_point_i64_i64(int64_t qx, int64_t qy);
void add_point_fast_i64_i64(int64_t qx, int64_t qy);
int64_t grid_key_f64_f64(double x, double y);
void add_point_slow_f64_f64(double x, double y);
int32_t compute_points_fast_i64_ptr_f64_ptr_f64(int64_t n, double* xs, double* ys);
void compute_points_slow_i64_ptr_f64_ptr_f64(int64_t n, double* xs, double* ys);
int64_t T_mod_i64(int64_t n);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t SCALE = 100000000000;
static const int64_t HASH_SIZE = 1048576;
static const int64_t HASH_MASK = 1048575;
static const int64_t MAX_POINTS = 600000;
static const int64_t MAX_REPS = 600000;
/* Module statics */
static int64_t* fact_mod = NULL;
static int64_t* inv_fact_mod = NULL;
static int64_t* pts_qx = NULL;
static int64_t* pts_qy = NULL;
static int32_t* pts_count = NULL;
static int64_t num_points = 0;
static int32_t* hash_buckets = NULL;
static int32_t* hash_next = NULL;
static double* reps_x = NULL;
static double* reps_y = NULL;
static int32_t* reps_cnt = NULL;
static int64_t num_reps = 0;
static int32_t* grid_buckets = NULL;
static int32_t* grid_next = NULL;
int64_t modpow_i64_i64_i64(int64_t b0, int64_t e0, int64_t m0) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((b0), (m0));
int64_t e = e0;
while (e > 0) {
if ((e & 1) != 0) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(b)))), (((__int128)(m0))))));
}
b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(m0))))));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t modinv_i64_i64(int64_t a, int64_t m) {
return modpow_i64_i64_i64(a, (m - 2), m);
}
void init_factorials(void) {
fact_mod = calloc(61, 8);
inv_fact_mod = calloc(61, 8);
fact_mod[0] = 1;
int64_t i = 1;
while (i <= 60) {
fact_mod[i] = FLOW_CHECKED_MOD(((fact_mod[(i - 1)] * i)), (MOD));
i = (i + 1);
}
i = 0;
while (i <= 60) {
inv_fact_mod[i] = modinv_i64_i64(fact_mod[i], MOD);
i = (i + 1);
}
}
int64_t comb_mod_i64_i64(int64_t n, int64_t k) {
if ((k < 0 || k > n)) {
return 0;
}
return ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((fact_mod[n] * inv_fact_mod[k])), (MOD)) * inv_fact_mod[(n - k)])), (MOD))));
}
int64_t cycles_at_least_two_edges_i64_i64(int64_t n, int64_t m) {
if (m < 2) {
return 0;
}
int64_t inv2 = modinv_i64_i64(2, MOD);
int64_t total = FLOW_CHECKED_MOD(((fact_mod[(n - 1)] * inv2)), (MOD));
int64_t c0 = 0;
int64_t k = 0;
while (k <= m) {
int64_t ak = 0;
if (k == 0) {
ak = total;
} else {
ak = FLOW_CHECKED_MOD(((modpow_i64_i64_i64(2, (k - 1), MOD) * fact_mod[((n - k) - 1)])), (MOD));
}
int64_t term = FLOW_CHECKED_MOD(((comb_mod_i64_i64(m, k) * ak)), (MOD));
if (FLOW_CHECKED_MOD((k), (2)) == 0) {
c0 = FLOW_CHECKED_MOD(((c0 + term)), (MOD));
} else {
c0 = FLOW_CHECKED_MOD((((c0 - FLOW_CHECKED_MOD((term), (MOD))) + MOD)), (MOD));
}
k = (k + 1);
}
int64_t c1 = 0;
k = 1;
while (k <= m) {
int64_t ak = FLOW_CHECKED_MOD(((modpow_i64_i64_i64(2, (k - 1), MOD) * fact_mod[((n - k) - 1)])), (MOD));
int64_t term = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((k * comb_mod_i64_i64(m, k))), (MOD)) * ak)), (MOD));
if (FLOW_CHECKED_MOD(((k - 1)), (2)) == 0) {
c1 = FLOW_CHECKED_MOD(((c1 + term)), (MOD));
} else {
c1 = FLOW_CHECKED_MOD((((c1 - FLOW_CHECKED_MOD((term), (MOD))) + MOD)), (MOD));
}
k = (k + 1);
}
return FLOW_CHECKED_MOD(((((total - c0) - FLOW_CHECKED_MOD((c1), (MOD))) + (2 * MOD))), (MOD));
}
int64_t isqrt_ll_i64(int64_t n) {
if (n < 0) {
return (-1);
}
if (n == 0) {
return 0;
}
int64_t x = 0;
int64_t bit = 1;
while (bit <= n) {
bit = FLOW_CHECKED_SHL((bit), (2));
}
bit = FLOW_CHECKED_SHR((bit), (2));
while (bit != 0) {
if (n >= (x + bit)) {
n = (n - (x + bit));
x = (FLOW_CHECKED_SHR((x), (1)) + bit);
} else {
x = FLOW_CHECKED_SHR((x), (1));
}
bit = FLOW_CHECKED_SHR((bit), (2));
}
return x;
}
int64_t inv_triangular_i64(int64_t q) {
int64_t disc = (1 + (8 * q));
int64_t r = isqrt_ll_i64(disc);
if ((r * r) != disc) {
return (-1);
}
if (FLOW_CHECKED_MOD(((1 + r)), (2)) != 0) {
return (-1);
}
return FLOW_CHECKED_DIV(((1 + r)), (2));
}
int64_t hash_key_i64_i64(int64_t qx, int64_t qy) {
int64_t h = ((qx * 1000000007) + qy);
int64_t hi = FLOW_CHECKED_SHR((((int64_t)(h))), (32));
int64_t lo = (h & 4294967295);
int64_t mixed = ((lo ^ hi) & HASH_MASK);
return mixed;
}
int64_t find_point_i64_i64(int64_t qx, int64_t qy) {
int64_t h = hash_key_i64_i64(qx, qy);
int64_t idx = ((int64_t)(hash_buckets[h]));
while (idx != (-1)) {
if ((pts_qx[idx] == qx && pts_qy[idx] == qy)) {
return idx;
}
idx = ((int64_t)(hash_next[idx]));
}
return (-1);
}
void add_point_fast_i64_i64(int64_t qx, int64_t qy) {
int64_t idx = find_point_i64_i64(qx, qy);
if (idx >= 0) {
pts_count[idx] = (pts_count[idx] + 1);
return;
}
idx = num_points;
num_points = (num_points + 1);
pts_qx[idx] = qx;
pts_qy[idx] = qy;
pts_count[idx] = 1;
int64_t h = hash_key_i64_i64(qx, qy);
hash_next[idx] = hash_buckets[h];
hash_buckets[h] = ((int32_t)(idx));
}
int64_t grid_key_f64_f64(double x, double y) {
int64_t ix = ((int64_t)(floor((x / 0.000001))));
int64_t iy = ((int64_t)(floor((y / 0.000001))));
int64_t h = ((ix * 1000000007) + iy);
int64_t hi = FLOW_CHECKED_SHR((((int64_t)(h))), (32));
int64_t lo = (h & 4294967295);
return ((lo ^ hi) & HASH_MASK);
}
void add_point_slow_f64_f64(double x, double y) {
int64_t ix = ((int64_t)(floor((x / 0.000001))));
int64_t iy = ((int64_t)(floor((y / 0.000001))));
int64_t dx = (-1);
while (dx <= 1) {
int64_t dy = (-1);
while (dy <= 1) {
int64_t cx = (ix + dx);
int64_t cy = (iy + dy);
int64_t h2 = ((cx * 1000000007) + cy);
int64_t hi = FLOW_CHECKED_SHR((((int64_t)(h2))), (32));
int64_t lo = (h2 & 4294967295);
int64_t h = ((lo ^ hi) & HASH_MASK);
int64_t idx = ((int64_t)(grid_buckets[h]));
while (idx != (-1)) {
double ddx = (x - reps_x[idx]);
double ddy = (y - reps_y[idx]);
if (((ddx * ddx) + (ddy * ddy)) <= 1e-18) {
reps_cnt[idx] = (reps_cnt[idx] + 1);
return;
}
idx = ((int64_t)(grid_next[idx]));
}
dy = (dy + 1);
}
dx = (dx + 1);
}
int64_t idx = num_reps;
num_reps = (num_reps + 1);
reps_x[idx] = x;
reps_y[idx] = y;
reps_cnt[idx] = 1;
int64_t h = grid_key_f64_f64(x, y);
grid_next[idx] = grid_buckets[h];
grid_buckets[h] = ((int32_t)(idx));
}
int32_t compute_points_fast_i64_ptr_f64_ptr_f64(int64_t n, double* xs, double* ys) {
num_points = 0;
int64_t i = 0;
while (i < HASH_SIZE) {
hash_buckets[i] = (-1);
i = (i + 1);
}
int64_t a = 0;
while (a < (n - 3)) {
double x1 = xs[a];
double y1 = ys[a];
int64_t b = (a + 1);
while (b < (n - 2)) {
double x3 = xs[b];
double y3 = ys[b];
double abx = (x3 - x1);
double aby = (y3 - y1);
int64_t c = (b + 1);
while (c < (n - 1)) {
double x2 = xs[c];
double y2 = ys[c];
double dx12 = (x2 - x1);
double dy12 = (y2 - y1);
int64_t d = (c + 1);
while (d < n) {
double x4 = xs[d];
double y4 = ys[d];
double dx34 = (x4 - x3);
double dy34 = (y4 - y3);
double denom = ((dx12 * dy34) - (dy12 * dx34));
if (fabs(denom) < 1e-18) {
d = (d + 1);
continue;
}
double t = (((abx * dy34) - (aby * dx34)) / denom);
double px = (x1 + (t * dx12));
double py = (y1 + (t * dy12));
int64_t qx = llround((px * ((double)(SCALE))));
int64_t qy = llround((py * ((double)(SCALE))));
add_point_fast_i64_i64(qx, qy);
d = (d + 1);
}
c = (c + 1);
}
b = (b + 1);
}
a = (a + 1);
}
i = 0;
while (i < num_points) {
if (inv_triangular_i64(((int64_t)(pts_count[i]))) < 0) {
return 0;
}
i = (i + 1);
}
return 1;
}
void compute_points_slow_i64_ptr_f64_ptr_f64(int64_t n, double* xs, double* ys) {
num_reps = 0;
int64_t i = 0;
while (i < HASH_SIZE) {
grid_buckets[i] = (-1);
i = (i + 1);
}
int64_t a = 0;
while (a < (n - 3)) {
double x1 = xs[a];
double y1 = ys[a];
int64_t b = (a + 1);
while (b < (n - 2)) {
double x3 = xs[b];
double y3 = ys[b];
double abx = (x3 - x1);
double aby = (y3 - y1);
int64_t c = (b + 1);
while (c < (n - 1)) {
double x2 = xs[c];
double y2 = ys[c];
double dx12 = (x2 - x1);
double dy12 = (y2 - y1);
int64_t d = (c + 1);
while (d < n) {
double x4 = xs[d];
double y4 = ys[d];
double dx34 = (x4 - x3);
double dy34 = (y4 - y3);
double denom = ((dx12 * dy34) - (dy12 * dx34));
if (fabs(denom) < 1e-18) {
d = (d + 1);
continue;
}
double t = (((abx * dy34) - (aby * dx34)) / denom);
double px = (x1 + (t * dx12));
double py = (y1 + (t * dy12));
add_point_slow_f64_f64(px, py);
d = (d + 1);
}
c = (c + 1);
}
b = (b + 1);
}
a = (a + 1);
}
}
int64_t T_mod_i64(int64_t n) {
if (n < 4) {
return 0;
}
double tau = (2.0 * 3.14159265358979323846);
double* xs = (double*)(calloc(60, 8));
double* ys = (double*)(calloc(60, 8));
int64_t k = 0;
while (k < n) {
xs[k] = cos(((tau * ((double)(k))) / ((double)(n))));
ys[k] = sin(((tau * ((double)(k))) / ((double)(n))));
k = (k + 1);
}
int64_t* dist_m = (int64_t*)(calloc(100, 8));
int64_t* dist_cnt = (int64_t*)(calloc(100, 8));
int64_t dist_size = 0;
int32_t fast = compute_points_fast_i64_ptr_f64_ptr_f64(n, xs, ys);
if (fast != 0) {
int64_t i = 0;
while (i < num_points) {
int64_t m = inv_triangular_i64(((int64_t)(pts_count[i])));
int64_t found = (-1);
int64_t j = 0;
while (j < dist_size) {
if (dist_m[j] == m) {
found = j;
break;
}
j = (j + 1);
}
if (found < 0) {
dist_m[dist_size] = m;
dist_cnt[dist_size] = 1;
dist_size = (dist_size + 1);
} else {
dist_cnt[found] = (dist_cnt[found] + 1);
}
i = (i + 1);
}
} else {
compute_points_slow_i64_ptr_f64_ptr_f64(n, xs, ys);
int64_t i = 0;
while (i < num_reps) {
int64_t m = inv_triangular_i64(((int64_t)(reps_cnt[i])));
if (m < 0) {
i = (i + 1);
continue;
}
int64_t found = (-1);
int64_t j = 0;
while (j < dist_size) {
if (dist_m[j] == m) {
found = j;
break;
}
j = (j + 1);
}
if (found < 0) {
dist_m[dist_size] = m;
dist_cnt[dist_size] = 1;
dist_size = (dist_size + 1);
} else {
dist_cnt[found] = (dist_cnt[found] + 1);
}
i = (i + 1);
}
}
int64_t total = 0;
int64_t i = 0;
while (i < dist_size) {
int64_t g = cycles_at_least_two_edges_i64_i64(n, dist_m[i]);
total = FLOW_CHECKED_MOD(((total + (dist_cnt[i] * g))), (MOD));
i = (i + 1);
}
free(xs);
free(ys);
free(dist_m);
free(dist_cnt);
return total;
}
int32_t main(void) {
init_factorials();
pts_qx = calloc(MAX_POINTS, 8);
pts_qy = calloc(MAX_POINTS, 8);
pts_count = calloc(MAX_POINTS, 4);
hash_buckets = calloc(HASH_SIZE, 4);
hash_next = calloc(MAX_POINTS, 4);
reps_x = calloc(MAX_REPS, 8);
reps_y = calloc(MAX_REPS, 8);
reps_cnt = calloc(MAX_REPS, 4);
grid_buckets = calloc(HASH_SIZE, 4);
grid_next = calloc(MAX_REPS, 4);
int64_t ans = 0;
int64_t n = 3;
while (n <= 60) {
ans = FLOW_CHECKED_MOD(((ans + T_mod_i64(n))), (MOD));
n = (n + 1);
}
printf("%lld\n", ans);
return 0;
}