# Project Euler 565
# Divisibility of Sum of Divisors
# Sum of n<=10^11 with sigma(n) divisible by 2017, via inclusion of trigger powers.
import euler.nt { isqrt }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function realloc(p: ptr<void>, size: i64) -> ptr<void>
}
function triangular(n: i64) -> i64 {
return n * (n + 1) / 2
}
function modpow(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut result: i64 = 1
let mut base: i64 = base0 % mod
let mut exp: i64 = exp0
while exp > 0 {
if (exp & 1) != 0 {
result = ((result as i128) * (base as i128) % (mod as i128)) as i64
}
base = ((base as i128) * (base as i128) % (mod as i128)) as i64
exp = exp >> 1
}
return result
}
function prime_factors_into(n0: i64, out: ptr<i64>) -> i64 {
let mut n: i64 = n0
let mut c: i64 = 0
let mut d: i64 = 2
while d * d <= n {
if n % d == 0 {
out[c] = d
c = c + 1
while n % d == 0 { n = n / d }
}
if d == 2 { d = 3 } else { d = d + 2 }
}
if n > 1 {
out[c] = n
c = c + 1
}
return c
}
function multiplicative_order(base: i64, modulo: i64, factors: ptr<i64>, nf: i64) -> i64 {
let mut order: i64 = modulo - 1
let residue: i64 = base % modulo
let mut i: i64 = 0
while i < nf {
let factor: i64 = factors[i]
while order % factor == 0 && modpow(residue, order / factor, modulo) == 1 {
order = order / factor
}
i = i + 1
}
return order
}
function single_event_sum(limit: i64, q: i64, q_power: i64) -> i64 {
let m: i64 = limit / q_power
return q_power * (triangular(m) - q * triangular(m / q))
}
function pair_event_sum(limit: i64, q: i64, q_power: i64, r: i64, r_power: i64) -> i64 {
let base: i64 = q_power * r_power
let m: i64 = limit / base
return base * (triangular(m) - q * triangular(m / q) - r * triangular(m / r) + q * r * triangular(m / (q * r)))
}
function search(limit: i64, modulo: i64) -> i64 {
let sqrt_lim: i64 = isqrt(limit)
let sieve: ptr<i8> = calloc(sqrt_lim + 1, 1)
if sieve == null { return -1 }
sieve[0] = 1
sieve[1] = 1
let mut p: i64 = 2
while p * p <= sqrt_lim {
if sieve[p] == 0 {
let mut m: i64 = p * p
while m <= sqrt_lim {
sieve[m] = 1
m = m + p
}
}
p = p + 1
}
let mut small_cap: i64 = 200000
let small_primes: ptr<i64> = calloc(small_cap, 8)
let mut nsp: i64 = 0
p = 2
while p <= sqrt_lim {
if sieve[p] == 0 {
small_primes[nsp] = p
nsp = nsp + 1
}
p = p + 1
}
free(sieve)
let factors: ptr<i64> = calloc(32, 8)
let nf: i64 = prime_factors_into(modulo - 1, factors)
# linear events: primes q <= limit with q ≡ -1 (mod modulo)
let max_k: i64 = (limit + 1) / modulo
let ksieve: ptr<i8> = calloc(max_k + 1, 1)
if ksieve == null { return -1 }
ksieve[0] = 1
let mut ii: i64 = 0
while ii < nsp {
let pp: i64 = small_primes[ii]
if pp != modulo {
let residue: i64 = modpow(modulo % pp, pp - 2, pp)
let min_k: i64 = (pp * pp + 1 + modulo - 1) / modulo
let mut res: i64 = residue
if res < min_k {
res = res + ((min_k - res + pp - 1) / pp) * pp
}
let mut kk: i64 = res
while kk <= max_k {
ksieve[kk] = 1
kk = kk + pp
}
}
ii = ii + 1
}
let mut lin_cap: i64 = max_k / 10 + 1000
let linear: ptr<i64> = calloc(lin_cap, 8)
let mut nlin: i64 = 0
let mut k: i64 = 1
while k <= max_k {
if ksieve[k] == 0 {
if nlin >= lin_cap {
lin_cap = lin_cap * 2
linear = realloc(linear, lin_cap * 8)
}
linear[nlin] = modulo * k - 1
nlin = nlin + 1
}
k = k + 1
}
free(ksieve)
# higher trigger powers
let mut hi_cap: i64 = 100000
let hq: ptr<i64> = calloc(hi_cap, 8)
let hp: ptr<i64> = calloc(hi_cap, 8)
let mut nhi: i64 = 0
ii = 0
while ii < nsp {
let q: i64 = small_primes[ii]
if q != modulo {
let residue: i64 = q % modulo
if residue != 1 {
let order: i64 = multiplicative_order(q, modulo, factors, nf)
let mut power: i64 = 1
let mut exponent: i64 = 0
while power <= limit / q {
power = power * q
exponent = exponent + 1
if (exponent + 1) % order == 0 {
if !(order == 2 && exponent == 1) {
if nhi >= hi_cap {
hi_cap = hi_cap * 2
hq = realloc(hq, hi_cap * 8)
hp = realloc(hp, hi_cap * 8)
}
hq[nhi] = q
hp[nhi] = power
nhi = nhi + 1
}
}
}
}
}
ii = ii + 1
}
# sort higher by power (insertion sort; nhi small)
let mut a: i64 = 1
while a < nhi {
let mut b: i64 = a
while b > 0 && hp[b - 1] > hp[b] {
let tq: i64 = hq[b]
let tp: i64 = hp[b]
hq[b] = hq[b - 1]
hp[b] = hp[b - 1]
hq[b - 1] = tq
hp[b - 1] = tp
b = b - 1
}
a = a + 1
}
let mut total: i64 = 0
ii = 0
while ii < nlin {
let q: i64 = linear[ii]
total = total + single_event_sum(limit, q, q)
ii = ii + 1
}
ii = 0
while ii < nhi {
total = total + single_event_sum(limit, hq[ii], hp[ii])
ii = ii + 1
}
ii = 0
while ii < nlin {
let q: i64 = linear[ii]
if q * q > limit { break }
# bisect_right linear for limit/q
let mut lo: i64 = ii + 1
let mut hi: i64 = nlin
let key: i64 = limit / q
while lo < hi {
let mid: i64 = (lo + hi) / 2
if linear[mid] <= key { lo = mid + 1 } else { hi = mid }
}
let mut jj: i64 = ii + 1
while jj < lo {
total = total - pair_event_sum(limit, q, q, linear[jj], linear[jj])
jj = jj + 1
}
ii = ii + 1
}
ii = 0
while ii < nhi {
let q: i64 = hq[ii]
let q_power: i64 = hp[ii]
let mut lo: i64 = 0
let mut hi: i64 = nlin
let key: i64 = limit / q_power
while lo < hi {
let mid: i64 = (lo + hi) / 2
if linear[mid] <= key { lo = mid + 1 } else { hi = mid }
}
let mut jj: i64 = 0
while jj < lo {
let r: i64 = linear[jj]
if r != q {
total = total - pair_event_sum(limit, q, q_power, r, r)
}
jj = jj + 1
}
ii = ii + 1
}
ii = 0
while ii < nhi {
let q: i64 = hq[ii]
let q_power: i64 = hp[ii]
if q_power * q_power > limit { break }
let mut jj: i64 = ii + 1
while jj < nhi {
let r: i64 = hq[jj]
let r_power: i64 = hp[jj]
if q_power * r_power > limit { break }
if q != r {
total = total - pair_event_sum(limit, q, q_power, r, r_power)
}
jj = jj + 1
}
ii = ii + 1
}
free(hp)
free(hq)
free(linear)
free(factors)
free(small_primes)
return total
}
function main() -> i32 {
printf("%lld\n", search(100000000000, 2017))
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 triangular_i64(int64_t n);
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int64_t prime_factors_into_i64_ptr_i64(int64_t n0, int64_t* out);
int64_t multiplicative_order_i64_i64_ptr_i64_i64(int64_t base, int64_t modulo, int64_t* factors, int64_t nf);
int64_t single_event_sum_i64_i64_i64(int64_t limit, int64_t q, int64_t q_power);
int64_t pair_event_sum_i64_i64_i64_i64_i64(int64_t limit, int64_t q, int64_t q_power, int64_t r, int64_t r_power);
int64_t search_i64_i64(int64_t limit, int64_t modulo);
int32_t main(void);
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 triangular_i64(int64_t n) {
return FLOW_CHECKED_DIV(((n * (n + 1))), (2));
}
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t result = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (mod));
int64_t exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
result = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(result)) * ((__int128)(base)))), (((__int128)(mod))))));
}
base = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(base)) * ((__int128)(base)))), (((__int128)(mod))))));
exp = FLOW_CHECKED_SHR((exp), (1));
}
return result;
}
int64_t prime_factors_into_i64_ptr_i64(int64_t n0, int64_t* out) {
int64_t n = n0;
int64_t c = 0;
int64_t d = 2;
while ((d * d) <= n) {
if (FLOW_CHECKED_MOD((n), (d)) == 0) {
out[c] = d;
c = (c + 1);
while (FLOW_CHECKED_MOD((n), (d)) == 0) {
n = FLOW_CHECKED_DIV((n), (d));
}
}
if (d == 2) {
d = 3;
} else {
d = (d + 2);
}
}
if (n > 1) {
out[c] = n;
c = (c + 1);
}
return c;
}
int64_t multiplicative_order_i64_i64_ptr_i64_i64(int64_t base, int64_t modulo, int64_t* factors, int64_t nf) {
int64_t order = (modulo - 1);
int64_t residue = FLOW_CHECKED_MOD((base), (modulo));
int64_t i = 0;
while (i < nf) {
int64_t factor = factors[i];
while ((FLOW_CHECKED_MOD((order), (factor)) == 0 && modpow_i64_i64_i64(residue, FLOW_CHECKED_DIV((order), (factor)), modulo) == 1)) {
order = FLOW_CHECKED_DIV((order), (factor));
}
i = (i + 1);
}
return order;
}
int64_t single_event_sum_i64_i64_i64(int64_t limit, int64_t q, int64_t q_power) {
int64_t m = FLOW_CHECKED_DIV((limit), (q_power));
return (q_power * (triangular_i64(m) - (q * triangular_i64(FLOW_CHECKED_DIV((m), (q))))));
}
int64_t pair_event_sum_i64_i64_i64_i64_i64(int64_t limit, int64_t q, int64_t q_power, int64_t r, int64_t r_power) {
int64_t base = (q_power * r_power);
int64_t m = FLOW_CHECKED_DIV((limit), (base));
return (base * (((triangular_i64(m) - (q * triangular_i64(FLOW_CHECKED_DIV((m), (q))))) - (r * triangular_i64(FLOW_CHECKED_DIV((m), (r))))) + ((q * r) * triangular_i64(FLOW_CHECKED_DIV((m), ((q * r)))))));
}
int64_t search_i64_i64(int64_t limit, int64_t modulo) {
int64_t sqrt_lim = isqrt_i64(limit);
int8_t* sieve = (int8_t*)(calloc((sqrt_lim + 1), 1));
if (sieve == NULL) {
return (-1);
}
sieve[0] = 1;
sieve[1] = 1;
int64_t p = 2;
while ((p * p) <= sqrt_lim) {
if (sieve[p] == 0) {
int64_t m = (p * p);
while (m <= sqrt_lim) {
sieve[m] = 1;
m = (m + p);
}
}
p = (p + 1);
}
int64_t small_cap = 200000;
int64_t* small_primes = (int64_t*)(calloc(small_cap, 8));
int64_t nsp = 0;
p = 2;
while (p <= sqrt_lim) {
if (sieve[p] == 0) {
small_primes[nsp] = p;
nsp = (nsp + 1);
}
p = (p + 1);
}
free(sieve);
int64_t* factors = (int64_t*)(calloc(32, 8));
int64_t nf = prime_factors_into_i64_ptr_i64((modulo - 1), factors);
int64_t max_k = FLOW_CHECKED_DIV(((limit + 1)), (modulo));
int8_t* ksieve = (int8_t*)(calloc((max_k + 1), 1));
if (ksieve == NULL) {
return (-1);
}
ksieve[0] = 1;
int64_t ii = 0;
while (ii < nsp) {
int64_t pp = small_primes[ii];
if (pp != modulo) {
int64_t residue = modpow_i64_i64_i64(FLOW_CHECKED_MOD((modulo), (pp)), (pp - 2), pp);
int64_t min_k = FLOW_CHECKED_DIV((((((pp * pp) + 1) + modulo) - 1)), (modulo));
int64_t res = residue;
if (res < min_k) {
res = (res + (FLOW_CHECKED_DIV(((((min_k - res) + pp) - 1)), (pp)) * pp));
}
int64_t kk = res;
while (kk <= max_k) {
ksieve[kk] = 1;
kk = (kk + pp);
}
}
ii = (ii + 1);
}
int64_t lin_cap = (FLOW_CHECKED_DIV((max_k), (10)) + 1000);
int64_t* linear = (int64_t*)(calloc(lin_cap, 8));
int64_t nlin = 0;
int64_t k = 1;
while (k <= max_k) {
if (ksieve[k] == 0) {
if (nlin >= lin_cap) {
lin_cap = (lin_cap * 2);
linear = realloc(linear, (lin_cap * 8));
}
linear[nlin] = ((modulo * k) - 1);
nlin = (nlin + 1);
}
k = (k + 1);
}
free(ksieve);
int64_t hi_cap = 100000;
int64_t* hq = (int64_t*)(calloc(hi_cap, 8));
int64_t* hp = (int64_t*)(calloc(hi_cap, 8));
int64_t nhi = 0;
ii = 0;
while (ii < nsp) {
int64_t q = small_primes[ii];
if (q != modulo) {
int64_t residue = FLOW_CHECKED_MOD((q), (modulo));
if (residue != 1) {
int64_t order = multiplicative_order_i64_i64_ptr_i64_i64(q, modulo, factors, nf);
int64_t power = 1;
int64_t exponent = 0;
while (power <= FLOW_CHECKED_DIV((limit), (q))) {
power = (power * q);
exponent = (exponent + 1);
if (FLOW_CHECKED_MOD(((exponent + 1)), (order)) == 0) {
if ((!((order == 2 && exponent == 1)))) {
if (nhi >= hi_cap) {
hi_cap = (hi_cap * 2);
hq = realloc(hq, (hi_cap * 8));
hp = realloc(hp, (hi_cap * 8));
}
hq[nhi] = q;
hp[nhi] = power;
nhi = (nhi + 1);
}
}
}
}
}
ii = (ii + 1);
}
int64_t a = 1;
while (a < nhi) {
int64_t b = a;
while ((b > 0 && hp[(b - 1)] > hp[b])) {
int64_t tq = hq[b];
int64_t tp = hp[b];
hq[b] = hq[(b - 1)];
hp[b] = hp[(b - 1)];
hq[(b - 1)] = tq;
hp[(b - 1)] = tp;
b = (b - 1);
}
a = (a + 1);
}
int64_t total = 0;
ii = 0;
while (ii < nlin) {
int64_t q = linear[ii];
total = (total + single_event_sum_i64_i64_i64(limit, q, q));
ii = (ii + 1);
}
ii = 0;
while (ii < nhi) {
total = (total + single_event_sum_i64_i64_i64(limit, hq[ii], hp[ii]));
ii = (ii + 1);
}
ii = 0;
while (ii < nlin) {
int64_t q = linear[ii];
if ((q * q) > limit) {
break;
}
int64_t lo = (ii + 1);
int64_t hi = nlin;
int64_t key = FLOW_CHECKED_DIV((limit), (q));
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (linear[mid] <= key) {
lo = (mid + 1);
} else {
hi = mid;
}
}
int64_t jj = (ii + 1);
while (jj < lo) {
total = (total - pair_event_sum_i64_i64_i64_i64_i64(limit, q, q, linear[jj], linear[jj]));
jj = (jj + 1);
}
ii = (ii + 1);
}
ii = 0;
while (ii < nhi) {
int64_t q = hq[ii];
int64_t q_power = hp[ii];
int64_t lo = 0;
int64_t hi = nlin;
int64_t key = FLOW_CHECKED_DIV((limit), (q_power));
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (linear[mid] <= key) {
lo = (mid + 1);
} else {
hi = mid;
}
}
int64_t jj = 0;
while (jj < lo) {
int64_t r = linear[jj];
if (r != q) {
total = (total - pair_event_sum_i64_i64_i64_i64_i64(limit, q, q_power, r, r));
}
jj = (jj + 1);
}
ii = (ii + 1);
}
ii = 0;
while (ii < nhi) {
int64_t q = hq[ii];
int64_t q_power = hp[ii];
if ((q_power * q_power) > limit) {
break;
}
int64_t jj = (ii + 1);
while (jj < nhi) {
int64_t r = hq[jj];
int64_t r_power = hp[jj];
if ((q_power * r_power) > limit) {
break;
}
if (q != r) {
total = (total - pair_event_sum_i64_i64_i64_i64_i64(limit, q, q_power, r, r_power));
}
jj = (jj + 1);
}
ii = (ii + 1);
}
free(hp);
free(hq);
free(linear);
free(factors);
free(small_primes);
return total;
}
int32_t main(void) {
printf("%lld\n", search_i64_i64(100000000000, 2017));
return 0;
}