Problem 344: Silver Dollar Game

Project Euler Problem 344 Solution

EulerSolve provides an optimized solution for Project Euler Problem 344, Silver Dollar Game, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary There are $m=c+1$ coins on a strip of $n$ squares, and exactly one of them is the silver dollar. A legal move is either a regular left move of one coin or the special move of pocketing the leftmost coin. The first player wins iff they eventually pocket the silver dollar. So we must count all configurations from which the first player can force that outcome. If we first choose the occupied squares and then choose which of the $m$ coins is silver, the total number of raw configurations is $$T=m\binom{n}{m}.$$ Mathematical Approach Gap Model Write the coin positions as $$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$ Instead of working with positions directly, the code switches to gaps: $$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$ These are the empty squares before the first coin, between consecutive coins, and after the last coin. Every legal placement corresponds to exactly one nonnegative gap vector $(g_0,\dots,g_m)$, and the total number of empty squares is $$g_0+g_1+\cdots+g_m=n-m=:N.$$ This is why the implementation begins with the parameter reduction $$m=c+1,\qquad N=n-m.$$ Ordinary Silver Dollar Positions as Nim Heaps The crucial combinatorial fact is that the ordinary silver dollar game can be described by alternating gaps ....

Detailed mathematical approach

Problem Summary

There are $m=c+1$ coins on a strip of $n$ squares, and exactly one of them is the silver dollar. A legal move is either a regular left move of one coin or the special move of pocketing the leftmost coin. The first player wins iff they eventually pocket the silver dollar.

So we must count all configurations from which the first player can force that outcome. If we first choose the occupied squares and then choose which of the $m$ coins is silver, the total number of raw configurations is

$$T=m\binom{n}{m}.$$

Mathematical Approach

Gap Model

Write the coin positions as

$$0\le x_0 \lt x_1 \lt \cdots \lt x_{m-1}\le n-1.$$

Instead of working with positions directly, the code switches to gaps:

$$g_0=x_0,\qquad g_i=x_i-x_{i-1}-1\ (1\le i\le m-1),\qquad g_m=n-1-x_{m-1}.$$

These are the empty squares before the first coin, between consecutive coins, and after the last coin. Every legal placement corresponds to exactly one nonnegative gap vector $(g_0,\dots,g_m)$, and the total number of empty squares is

$$g_0+g_1+\cdots+g_m=n-m=:N.$$

This is why the implementation begins with the parameter reduction

$$m=c+1,\qquad N=n-m.$$

Ordinary Silver Dollar Positions as Nim Heaps

The crucial combinatorial fact is that the ordinary silver dollar game can be described by alternating gaps. Let

$$k=\left\lceil\frac{m}{2}\right\rceil,\qquad r=m-k+1.$$

The active gaps are the ones that contribute to the Nim-style xor condition:

If $m$ is even, the active gaps are

$$g_1,g_3,\dots,g_{m-1}.$$

If $m$ is odd, the active gaps are

$$g_0,g_2,\dots,g_{m-1}.$$

All remaining gaps are passive: they affect the total length, but not the xor criterion.

For the ordinary silver dollar game, a position is losing precisely when the xor of the active gaps is zero:

$$a_1\oplus a_2\oplus\cdots\oplus a_k=0,$$

where $\oplus$ denotes bitwise xor, i.e. the Nim-sum. This reduces the geometric game on coin positions to a counting problem on nonnegative integers with a fixed total sum and an xor constraint.

How the Pocket Rule Changes the Losing Positions

Now restore the fact that one coin is distinguished as the silver dollar, and let $j\in\{0,\dots,m-1\}$ be its rank from the left.

1) The leftmost silver dollar is never losing. If $j=0$, the current player pockets it immediately and wins.

2) Even number of coins. If $m$ is even and $j\ge1$, the losing configurations are exactly the ordinary xor-zero gap configurations. The silver dollar may be any of the $m-1$ non-leftmost coins, so

$$L=(m-1)L_0,\qquad L_0=\text{Count}(N;\text{ways}_k).$$

3) Odd number of coins. If $m$ is odd, two different families appear:

When the silver dollar is the second coin ($j=1$), we again obtain the ordinary xor-zero count

$$L_0=\text{Count}(N;\text{ways}_k).$$

When the silver dollar is any coin from the third onward ($j\ge2$), the pocket move shifts the effective left boundary by one square. In gap language this becomes the same xor-zero counting problem, but with total sum $N+1$ and the extra requirement $g_0>0$. The code denotes this count by $L_1$:

$$L_1=\text{Count}(N+1;\text{ways}_k)-\text{Count}(N+1;\text{ways}_{k-1}).$$

The subtraction removes the cases with $g_0=0$: if the first active gap is zero, it contributes nothing to the xor and the problem collapses to the same count with only $k-1$ active gaps.

Therefore, for odd $m$,

$$L=L_0+(m-2)L_1.$$

Finally the number of winning configurations is always

$$W=T-L.$$

Counting the Xor-Zero Gap Tuples

The function $\text{Count}(S;\text{ways})$ counts nonnegative gap tuples whose total sum is $S$ and whose active gaps xor to zero. Direct enumeration is impossible for $n=10^6$, so the code counts them bit by bit.

Fix one binary column. Suppose exactly $x$ of the $k$ active gaps have bit 1. To keep xor zero in that column, $x$ must be even. If exactly $y$ of the $r$ passive gaps also have bit 1, then the total number of ones in that column is $s=x+y$, and the number of assignments for that column is

$$\binom{k}{x}\binom{r}{y}.$$

Summing over all even $x$ gives the coefficient array used by the DP:

$$\text{ways}(s)=\sum_{\substack{0\le x\le k\\x\text{ even}}}\binom{k}{x}\binom{r}{s-x},\qquad 0\le s\le k+r.$$

This explains the code in build_ways_even_*: it is not an arbitrary precomputation, but the exact count of all valid bit-column patterns.

Binary Carry Dynamic Programming

After the bit-column counts are known, the remaining task is to ensure that the total arithmetic sum of all gaps is exactly $S$. That is what count_with_ways does.

Process the binary expansion of $S$ from least significant bit to most significant bit. Let $c$ be the incoming carry at bit $b$, and let $\beta_b\in\{0,1\}$ be the $b$-th bit of $S$. If a chosen column has $s$ ones in total, then it is valid exactly when

$$s+c\equiv \beta_b\pmod2.$$

The outgoing carry is then

$$c'=\frac{s+c-\beta_b}{2}.$$

Hence the transition is

$$dp_{b+1}(c')\mathrel{+}=dp_b(c)\cdot \text{ways}(s).$$

This is a standard digit-DP with carries, but here the column multiplicities already encode the xor-zero condition on the active gaps.

Worked Example: $W(10,2)=324$

Here $m=c+1=3$ and $N=n-m=7$. The total number of configurations is

$$T=3\binom{10}{3}=3\cdot120=360.$$

Because $m$ is odd, the losing count splits into two parts. The silver dollar on the second coin contributes

$$L_0=\text{Count}(7;\text{ways}_2)=20.$$

The silver dollar on the third coin contributes

$$L_1=\text{Count}(8;\text{ways}_2)-\text{Count}(8;\text{ways}_1)=16.$$

Therefore

$$L=20+(3-2)\cdot16=36,$$

and

$$W=360-36=324,$$

which matches the published checkpoint.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First, they build small binomial tables for the gap-layer coefficients. Next, build_ways_even_* constructs the array $\text{ways}(s)$. Then count_with_ways_* performs the carry DP for an exact target sum. Finally, compute_W_* applies the even/odd formulas for the losing count and subtracts it from $T$.

For the final Euler input, the modulus is composite:

$$M=1000036000099=1000003\cdot1000033.$$

So the code computes binomial coefficients modulo each prime via factorial and inverse-factorial tables, then merges the two residues with the Chinese Remainder Theorem. The C++ version additionally computes the small checkpoints exactly before switching to modular arithmetic for $W(1\,000\,000,100)$.

Complexity Analysis

For fixed $m$, a single Count call scans $O(\log N)$ bit levels. Each level considers $O(m)$ carry states and $O(m)$ possible column sums, so the DP cost is

$$O(m^2\log N)$$

time and $O(m)$ memory. The factorial / inverse-factorial preprocessing for modular binomial coefficients is $O(n)$ for each prime modulus.

Problem 344 source code

C++

#include <algorithm>
#include <cstdint>
#include <future>
#include <iostream>
#include <string>
#include <vector>

using u128 = unsigned __int128;

namespace {

constexpr uint64_t kMod = 1000036000099ULL;
constexpr uint64_t kP1 = 1000003ULL;
constexpr uint64_t kP2 = 1000033ULL;

struct SmallComb {
    std::vector<std::vector<unsigned long long>> c;
};

SmallComb build_small_comb(int max_n) {
    SmallComb comb;
    comb.c.assign(max_n + 1, std::vector<unsigned long long>(max_n + 1, 0));
    for (int n = 0; n <= max_n; ++n) {
        comb.c[n][0] = comb.c[n][n] = 1;
        for (int k = 1; k < n; ++k) {
            comb.c[n][k] = comb.c[n - 1][k - 1] + comb.c[n - 1][k];
        }
    }
    return comb;
}

uint64_t mod_pow(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    while (exp > 0) {
        if (exp & 1) result = static_cast<uint64_t>((u128)result * base % mod);
        base = static_cast<uint64_t>((u128)base * base % mod);
        exp >>= 1;
    }
    return result;
}

uint64_t mod_inv_prime(uint64_t a, uint64_t p) {
    return mod_pow(a, p - 2, p);
}

struct FactTable {
    std::vector<uint64_t> fact;
    std::vector<uint64_t> invfact;
};

FactTable build_fact_table(int n, uint64_t p) {
    FactTable ft;
    ft.fact.resize(n + 1);
    ft.invfact.resize(n + 1);
    ft.fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        ft.fact[i] = static_cast<uint64_t>((u128)ft.fact[i - 1] * i % p);
    }
    ft.invfact[n] = mod_pow(ft.fact[n], p - 2, p);
    for (int i = n; i >= 1; --i) {
        ft.invfact[i - 1] = static_cast<uint64_t>((u128)ft.invfact[i] * i % p);
    }
    return ft;
}

uint64_t binom_mod_prime(int n, int k, const FactTable& ft, uint64_t p) {
    if (k < 0 || k > n) return 0;
    uint64_t res = static_cast<uint64_t>((u128)ft.fact[n] * ft.invfact[k] % p);
    res = static_cast<uint64_t>((u128)res * ft.invfact[n - k] % p);
    return res;
}

uint64_t crt(uint64_t a, uint64_t b) {
    uint64_t t = (b + kP2 - (a % kP2)) % kP2;
    uint64_t inv = mod_inv_prime(kP1 % kP2, kP2);
    uint64_t k = static_cast<uint64_t>((u128)t * inv % kP2);
    return static_cast<uint64_t>((u128)a + (u128)kP1 * k);
}

uint64_t binom_mod_composite(int n, int k, const FactTable& f1, const FactTable& f2) {
    uint64_t a = binom_mod_prime(n, k, f1, kP1);
    uint64_t b = binom_mod_prime(n, k, f2, kP2);
    return crt(a, b);
}

struct WaysEvenMod {
    int max_s = 0;
    std::vector<uint64_t> ways;
};

WaysEvenMod build_ways_even_mod(int k, int r, const SmallComb& comb) {
    WaysEvenMod out;
    out.max_s = k + r;
    out.ways.assign(out.max_s + 1, 0);
    for (int x = 0; x <= k; x += 2) {
        unsigned long long cx = comb.c[k][x];
        for (int y = 0; y <= r; ++y) {
            int s = x + y;
            u128 add = static_cast<u128>(cx) * comb.c[r][y];
            uint64_t val = static_cast<uint64_t>(add % kMod);
            uint64_t sum = out.ways[s] + val;
            if (sum >= kMod) sum -= kMod;
            out.ways[s] = sum;
        }
    }
    return out;
}

int bit_length(long long v) {
    int bits = 0;
    while (v > 0) {
        ++bits;
        v >>= 1;
    }
    return bits == 0 ? 1 : bits;
}

uint64_t count_with_ways_mod(long long S, const WaysEvenMod& ways) {
    int max_s = ways.max_s;
    std::vector<uint64_t> dp(max_s + 1, 0);
    std::vector<uint64_t> next(max_s + 1, 0);
    dp[0] = 1;

    int bits = bit_length(S) + 7; // flush remaining carry.
    for (int b = 0; b < bits; ++b) {
        int bit = static_cast<int>((S >> b) & 1LL);
        std::fill(next.begin(), next.end(), 0);
        for (int carry = 0; carry <= max_s; ++carry) {
            uint64_t base = dp[carry];
            if (base == 0) continue;
            for (int s = 0; s <= max_s; ++s) {
                uint64_t ways_s = ways.ways[s];
                if (ways_s == 0) continue;
                int total = s + carry;
                if ((total & 1) != bit) continue;
                int carry_out = total >> 1;
                uint64_t add = static_cast<uint64_t>((u128)base * ways_s % kMod);
                uint64_t sum = next[carry_out] + add;
                if (sum >= kMod) sum -= kMod;
                next[carry_out] = sum;
            }
        }
        dp.swap(next);
    }
    return dp[0];
}

struct WaysEvenExact {
    int max_s = 0;
    std::vector<u128> ways;
};

WaysEvenExact build_ways_even_exact(int k, int r, const SmallComb& comb) {
    WaysEvenExact out;
    out.max_s = k + r;
    out.ways.assign(out.max_s + 1, 0);
    for (int x = 0; x <= k; x += 2) {
        u128 cx = comb.c[k][x];
        for (int y = 0; y <= r; ++y) {
            int s = x + y;
            out.ways[s] += cx * comb.c[r][y];
        }
    }
    return out;
}

u128 count_with_ways_exact(long long S, const WaysEvenExact& ways) {
    int max_s = ways.max_s;
    std::vector<u128> dp(max_s + 1, 0);
    std::vector<u128> next(max_s + 1, 0);
    dp[0] = 1;

    int bits = bit_length(S) + 7;
    for (int b = 0; b < bits; ++b) {
        int bit = static_cast<int>((S >> b) & 1LL);
        std::fill(next.begin(), next.end(), 0);
        for (int carry = 0; carry <= max_s; ++carry) {
            u128 base = dp[carry];
            if (base == 0) continue;
            for (int s = 0; s <= max_s; ++s) {
                u128 ways_s = ways.ways[s];
                if (ways_s == 0) continue;
                int total = s + carry;
                if ((total & 1) != bit) continue;
                int carry_out = total >> 1;
                next[carry_out] += base * ways_s;
            }
        }
        dp.swap(next);
    }
    return dp[0];
}

u128 binom_exact(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    u128 res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * static_cast<u128>(n - k + i) / static_cast<u128>(i);
    }
    return res;
}

u128 compute_W_exact(int n, int c, const SmallComb& comb) {
    int m = c + 1;
    long long N = n - m;
    u128 total = static_cast<u128>(m) * binom_exact(n, m);
    if (m == 1) return total;

    int k = (m + 1) / 2;
    int r = m - k + 1;
    if (m % 2 == 0) {
        WaysEvenExact ways = build_ways_even_exact(k, r, comb);
        u128 losing = static_cast<u128>(m - 1) * count_with_ways_exact(N, ways);
        return total - losing;
    }

    WaysEvenExact ways_k = build_ways_even_exact(k, r, comb);
    WaysEvenExact ways_km1 = build_ways_even_exact(k - 1, r, comb);
    u128 L0 = count_with_ways_exact(N, ways_k);
    u128 L1 = count_with_ways_exact(N + 1, ways_k) - count_with_ways_exact(N + 1, ways_km1);
    u128 losing = L0 + static_cast<u128>(m - 2) * L1;
    return total - losing;
}

uint64_t compute_W_mod(int n, int c, const SmallComb& comb,
                       const FactTable& f1, const FactTable& f2) {
    int m = c + 1;
    long long N = n - m;
    uint64_t total = static_cast<uint64_t>((u128)m * binom_mod_composite(n, m, f1, f2) % kMod);
    if (m == 1) return total;

    int k = (m + 1) / 2;
    int r = m - k + 1;
    if (m % 2 == 0) {
        WaysEvenMod ways = build_ways_even_mod(k, r, comb);
        uint64_t losing = static_cast<uint64_t>((u128)(m - 1) * count_with_ways_mod(N, ways) % kMod);
        return (total + kMod - losing) % kMod;
    }

    WaysEvenMod ways_k = build_ways_even_mod(k, r, comb);
    WaysEvenMod ways_km1 = build_ways_even_mod(k - 1, r, comb);

    auto fut0 = std::async(std::launch::async, [&]() { return count_with_ways_mod(N, ways_k); });
    auto fut1 = std::async(std::launch::async, [&]() { return count_with_ways_mod(N + 1, ways_k); });
    auto fut2 = std::async(std::launch::async, [&]() { return count_with_ways_mod(N + 1, ways_km1); });

    uint64_t L0 = fut0.get();
    uint64_t L1 = fut1.get();
    uint64_t L1_sub = fut2.get();
    L1 = (L1 + kMod - L1_sub) % kMod;

    uint64_t losing = (L0 + static_cast<uint64_t>((u128)(m - 2) * L1 % kMod)) % kMod;
    return (total + kMod - losing) % kMod;
}

std::string to_string_u128(u128 v) {
    if (v == 0) return "0";
    std::string s;
    while (v > 0) {
        int digit = static_cast<int>(v % 10);
        s.push_back(static_cast<char>('0' + digit));
        v /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

} // namespace

int main() {
    const int max_small = 52;
    SmallComb comb = build_small_comb(max_small);

    std::cout << "--- Validation Checkpoints ---\n";
    u128 v1 = compute_W_exact(10, 2, comb);
    u128 v2 = compute_W_exact(100, 10, comb);
    std::cout << "W(10, 2) = " << to_string_u128(v1)
              << (v1 == 324 ? " [PASS]" : " [FAIL]") << "\n";
    std::cout << "W(100, 10) = " << to_string_u128(v2)
              << (v2 == 1514704946113500ULL ? " [PASS]" : " [FAIL]") << "\n";

    std::cout << "\n--- Final Solution ---\n";
    const int n = 1000000;
    const int c = 100;
    FactTable f1 = build_fact_table(n, kP1);
    FactTable f2 = build_fact_table(n, kP2);

    uint64_t result = compute_W_mod(n, c, comb, f1, f2);
    std::cout << "W(" << n << ", " << c << ") mod " << kMod << " = " << result << "\n";
    return 0;
}

Python

def bit_length(v):
    bits = 0
    while v > 0:
        bits += 1
        v >>= 1
    return 1 if bits == 0 else bits

kMod = 1000036000099
kP1 = 1000003
kP2 = 1000033

class SmallComb:
    def __init__(self, max_n):
        self.c = [[0] * (max_n + 1) for _ in range(max_n + 1)]
        for n in range(max_n + 1):
            self.c[n][0] = self.c[n][n] = 1
            for k in range(1, n):
                self.c[n][k] = self.c[n - 1][k - 1] + self.c[n - 1][k]

def build_small_comb(max_n):
    return SmallComb(max_n)

def mod_pow(base, exp, mod):
    return pow(base, exp, mod)

def mod_inv_prime(a, p):
    return pow(a, p - 2, p)

class FactTable:
    def __init__(self, n, p):
        self.fact = [0] * (n + 1)
        self.invfact = [0] * (n + 1)
        self.fact[0] = 1
        for i in range(1, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % p
        self.invfact[n] = mod_inv_prime(self.fact[n], p)
        for i in range(n, 0, -1):
            self.invfact[i - 1] = (self.invfact[i] * i) % p

def build_fact_table(n, p):
    return FactTable(n, p)

def binom_mod_prime(n, k, ft, p):
    if k < 0 or k > n: return 0
    res = (ft.fact[n] * ft.invfact[k]) % p
    res = (res * ft.invfact[n - k]) % p
    return res

def crt(a, b):
    t = (b + kP2 - (a % kP2)) % kP2
    inv = mod_inv_prime(kP1 % kP2, kP2)
    k = (t * inv) % kP2
    return a + kP1 * k

def binom_mod_composite(n, k, f1, f2):
    a = binom_mod_prime(n, k, f1, kP1)
    b = binom_mod_prime(n, k, f2, kP2)
    return crt(a, b)

class WaysEvenMod:
    def __init__(self, k, r, comb):
        self.max_s = k + r
        self.ways = [0] * (self.max_s + 1)
        for x in range(0, k + 1, 2):
            cx = comb.c[k][x]
            for y in range(0, r + 1):
                s = x + y
                add = (cx * comb.c[r][y]) % kMod
                self.ways[s] = (self.ways[s] + add) % kMod

def build_ways_even_mod(k, r, comb):
    return WaysEvenMod(k, r, comb)

def count_with_ways_mod(S, ways):
    max_s = ways.max_s
    dp = [0] * (max_s + 1)
    dp[0] = 1
    
    bits = bit_length(S) + 7
    for b in range(bits):
        bit = (S >> b) & 1
        nxt = [0] * (max_s + 1)
        for carry in range(max_s + 1):
            base = dp[carry]
            if base == 0: continue
            for s in range(max_s + 1):
                ways_s = ways.ways[s]
                if ways_s == 0: continue
                total = s + carry
                if (total & 1) != bit: continue
                carry_out = total >> 1
                add = (base * ways_s) % kMod
                nxt[carry_out] = (nxt[carry_out] + add) % kMod
        dp = nxt
    return dp[0]

def compute_W_mod(n, c, comb, f1, f2):
    m = c + 1
    N = n - m
    total = (m * binom_mod_composite(n, m, f1, f2)) % kMod
    if m == 1:
        return total
        
    k = (m + 1) // 2
    r = m - k + 1
    if m % 2 == 0:
        ways = build_ways_even_mod(k, r, comb)
        losing = ((m - 1) * count_with_ways_mod(N, ways)) % kMod
        return (total + kMod - losing) % kMod
        
    ways_k = build_ways_even_mod(k, r, comb)
    ways_km1 = build_ways_even_mod(k - 1, r, comb)
    
    L0 = count_with_ways_mod(N, ways_k)
    L1 = count_with_ways_mod(N + 1, ways_k)
    L1_sub = count_with_ways_mod(N + 1, ways_km1)
    L1 = (L1 + kMod - L1_sub) % kMod
    
    losing = (L0 + ((m - 2) * L1) % kMod) % kMod
    return (total + kMod - losing) % kMod

def solve():
    max_small = 52
    comb = build_small_comb(max_small)
    n = 1000000
    c = 100
    f1 = build_fact_table(n, kP1)
    f2 = build_fact_table(n, kP2)
    ans = compute_W_mod(n, c, comb, f1, f2)
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler344 {

    static final long MOD = 1000036000099L;
    static final long P1 = 1000003L;
    static final long P2 = 1000033L;

    static class SmallComb {
        long[][] c;

        SmallComb(int maxN) {
            c = new long[maxN + 1][maxN + 1];
            for (int n = 0; n <= maxN; n++) {
                c[n][0] = c[n][n] = 1;
                for (int k = 1; k < n; k++) {
                    c[n][k] = c[n - 1][k - 1] + c[n - 1][k];
                }
            }
        }
    }

    static long modPow(long base, long exp, long mod) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1)
                result = mulMod(result, base, mod);
            base = mulMod(base, base, mod);
            exp >>= 1;
        }
        return result;
    }

    static long mulMod(long a, long b, long mod) {
        return (long) ((((java.math.BigInteger.valueOf(a)).multiply(java.math.BigInteger.valueOf(b)))
                .remainder(java.math.BigInteger.valueOf(mod))).longValue());
    }

    static long modInvPrime(long a, long p) {
        return modPow(a, p - 2, p);
    }

    static class FactTable {
        long[] fact;
        long[] invfact;

        FactTable(int n, long p) {
            fact = new long[n + 1];
            invfact = new long[n + 1];
            fact[0] = 1;
            for (int i = 1; i <= n; i++) {
                fact[i] = (fact[i - 1] * i) % p;
            }
            invfact[n] = modInvPrime(fact[n], p);
            for (int i = n; i >= 1; i--) {
                invfact[i - 1] = (invfact[i] * i) % p;
            }
        }
    }

    static long binomModPrime(int n, int k, FactTable ft, long p) {
        if (k < 0 || k > n)
            return 0;
        long res = (ft.fact[n] * ft.invfact[k]) % p;
        res = (res * ft.invfact[n - k]) % p;
        return res;
    }

    static long crt(long a, long b) {
        long t = (b + P2 - (a % P2)) % P2;
        long inv = modInvPrime(P1 % P2, P2);
        long k = (t * inv) % P2;
        return a + P1 * k;
    }

    static long binomModComposite(int n, int k, FactTable f1, FactTable f2) {
        long a = binomModPrime(n, k, f1, P1);
        long b = binomModPrime(n, k, f2, P2);
        return crt(a, b);
    }

    static class WaysEvenMod {
        int max_s;
        long[] ways;

        WaysEvenMod(int k, int r, SmallComb comb) {
            max_s = k + r;
            ways = new long[max_s + 1];
            for (int x = 0; x <= k; x += 2) {
                long cx = comb.c[k][x];
                for (int y = 0; y <= r; y++) {
                    int s = x + y;
                    long add = mulMod(cx, comb.c[r][y], MOD);
                    ways[s] = (ways[s] + add) % MOD;
                }
            }
        }
    }

    static int bitLength(long v) {
        int bits = 0;
        while (v > 0) {
            bits++;
            v >>= 1;
        }
        return bits == 0 ? 1 : bits;
    }

    static long countWithWaysMod(long S, WaysEvenMod ways) {
        int max_s = ways.max_s;
        long[] dp = new long[max_s + 1];
        long[] next = new long[max_s + 1];
        dp[0] = 1;

        int bits = bitLength(S) + 7;
        for (int b = 0; b < bits; b++) {
            int bit = (int) ((S >> b) & 1L);
            Arrays.fill(next, 0);
            for (int carry = 0; carry <= max_s; carry++) {
                long base = dp[carry];
                if (base == 0)
                    continue;
                for (int s = 0; s <= max_s; s++) {
                    long ways_s = ways.ways[s];
                    if (ways_s == 0)
                        continue;
                    int total = s + carry;
                    if ((total & 1) != bit)
                        continue;
                    int carryOut = total >> 1;
                    long add = mulMod(base, ways_s, MOD);
                    next[carryOut] = (next[carryOut] + add) % MOD;
                }
            }
            long[] temp = dp;
            dp = next;
            next = temp;
        }
        return dp[0];
    }

    static long computeWMod(int n, int c, SmallComb comb, FactTable f1, FactTable f2) {
        int m = c + 1;
        long N = n - m;
        long total = mulMod(m, binomModComposite(n, m, f1, f2), MOD);
        if (m == 1)
            return total;

        int k = (m + 1) / 2;
        int r = m - k + 1;
        if (m % 2 == 0) {
            WaysEvenMod ways = new WaysEvenMod(k, r, comb);
            long losing = mulMod(m - 1, countWithWaysMod(N, ways), MOD);
            return (total + MOD - losing) % MOD;
        }

        WaysEvenMod ways_k = new WaysEvenMod(k, r, comb);
        WaysEvenMod ways_km1 = new WaysEvenMod(k - 1, r, comb);

        long L0 = countWithWaysMod(N, ways_k);
        long L1 = countWithWaysMod(N + 1, ways_k);
        long L1_sub = countWithWaysMod(N + 1, ways_km1);
        L1 = (L1 + MOD - L1_sub) % MOD;

        long losing = (L0 + mulMod(m - 2, L1, MOD)) % MOD;
        return (total + MOD - losing) % MOD;
    }

    public static String solve() {
        int maxSmall = 52;
        SmallComb comb = new SmallComb(maxSmall);
        int n = 1000000;
        int c = 100;
        FactTable f1 = new FactTable(n, P1);
        FactTable f2 = new FactTable(n, P2);

        long ans = computeWMod(n, c, comb, f1, f2);
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}