Problem 949: Left vs Right II

Project Euler Problem 949 Solution

EulerSolve provides an optimized solution for Project Euler Problem 949, Left vs Right II, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Problem 949 assigns a recursive left-versus-right position to every binary word $w$ of length $n$. The one-bit words are the starting numbers $0\mapsto +1$ and $1\mapsto -1$. For longer words, the recurrence treats proper suffixes as options on one side of the game and proper prefixes as options on the other. The implementations do not keep the full game tree; instead, they compute a signed score $u(w)$ together with a cold/non-cold classification. The target quantity is $G(20,7)\bmod 1001001011$. Direct enumeration is impossible: there are $2^{20}$ words of length 20 and therefore $(2^{20})^7$ ordered 7-tuples. The successful strategy is to evaluate each single word once, compress equal scores into histograms, and then count tuples by convolving those histograms. Mathematical Approach All three implementations follow the same two-stage plan. First they solve the single-word recurrence for every binary string up to length $n$. Then they turn the multiset of resulting scores into a counting problem on discrete distributions. The recursive bounds from shorter words For a word $w$ of length $\ell\ge 2$, let $\mathrm{Suf}(w)$ be the set of proper suffixes of $w$, and let $\mathrm{Pre}(w)$ be the set of proper prefixes. Every such option is shorter than $w$, so a bottom-up dynamic program by increasing length is valid....

Detailed mathematical approach

Problem Summary

Problem 949 assigns a recursive left-versus-right position to every binary word $w$ of length $n$. The one-bit words are the starting numbers $0\mapsto +1$ and $1\mapsto -1$. For longer words, the recurrence treats proper suffixes as options on one side of the game and proper prefixes as options on the other. The implementations do not keep the full game tree; instead, they compute a signed score $u(w)$ together with a cold/non-cold classification.

The target quantity is $G(20,7)\bmod 1001001011$. Direct enumeration is impossible: there are $2^{20}$ words of length 20 and therefore $(2^{20})^7$ ordered 7-tuples. The successful strategy is to evaluate each single word once, compress equal scores into histograms, and then count tuples by convolving those histograms.

Mathematical Approach

All three implementations follow the same two-stage plan. First they solve the single-word recurrence for every binary string up to length $n$. Then they turn the multiset of resulting scores into a counting problem on discrete distributions.

The recursive bounds from shorter words

For a word $w$ of length $\ell\ge 2$, let $\mathrm{Suf}(w)$ be the set of proper suffixes of $w$, and let $\mathrm{Pre}(w)$ be the set of proper prefixes. Every such option is shorter than $w$, so a bottom-up dynamic program by increasing length is valid.

Each shorter word $t$ carries two stored endpoints $u(t)$ and $d(t)$. The new raw bounds are

$$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$$

The one-bit layer is initialized as

$$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$$

after a global scaling that will be described next. Those formulas are the real core of the problem: every later value is forced by the best suffix-side bound and the best prefix-side bound coming from shorter words.

Why a dyadic grid is enough

The solutions represent every value on the dyadic grid with denominator dividing $2^n$. Instead of storing a rational number directly, they multiply everything by $2^n$ and store integers. A dyadic number $p/2^m$ is therefore encoded as $p\,2^{\,n-m}$.

This choice makes all comparisons exact and keeps the recurrence purely integer-based. The floor and ceiling operations that appear when searching for a new value become simple divisions by powers of two. Because the recursion depth is at most $n$, this dyadic representation is sufficient for every value created by the algorithm.

Cold states and the canonical value inside a strict gap

If the raw bounds satisfy

$$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$$

then the word falls into the cold bucket. In that case the implementations choose a single canonical dyadic number $x$ strictly between those two bounds and set

$$u(w)=d(w)=x.$$

The chosen $x$ is the simplest dyadic in the open interval $(u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))$: the search tries coarse denominators first, so the first successful scale gives the smallest denominator; within that scale it prefers $0$ if available, otherwise the admissible numerator closest to $0$; and for non-integer dyadics it keeps the numerator odd so the representation is already reduced.

If there is no strict gap, the state is kept as non-cold and the implementations simply store

$$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$$

This distinction matters later: only the cold states collapse to one exact number, while the non-cold states retain only their left-end score $u(w)$ for the final count.

Histogram compression of the final layer

Once all words of length $n$ have been processed, only two pieces of information are needed for each word: its stored score $u(w)$ and whether it was cold. The implementations therefore compress the full layer into two histograms,

$$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$$

$$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\text{ and }w\text{ is cold}\}.$$

This is the step that removes the exponential blow-up in $k$. Many different words share the same score, so the tuple problem can be solved on score frequencies instead of on individual words.

Turning $k$-tuples into convolution counts

For odd $k$, set

$$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$$

Let $D_a$ and $D_b$ be the $a$-fold and $b$-fold convolutions of $H_{\mathrm{all}}$, and let $C_a$ and $C_b$ be the corresponding convolution powers of $H_{\mathrm{cold}}$. Thus $D_a(s)$ is the number of ordered $a$-tuples of length-$n$ words whose stored scores sum to $s$, and similarly for the other distributions.

The answer is then

$$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$$

The first term counts all ordered $k$-tuples whose total stored score is negative. The second term adds the exact-zero cases, but only when every component comes from the cold histogram. Splitting the tuple into an $a$-part and a $b$-part is only a counting device; it preserves the total sum because $a+b=k$.

Worked example: why $G(2,3)=14$

For $n=2$, the global scale is $2^2=4$. The four binary words are $00,01,10,11$.

For $00$, both the only proper suffix and the only proper prefix are $0$, so the stored score is $+4$. For $11$, the same reasoning gives $-4$. For $01$, the suffix contributes $-4$ and the prefix contributes $+4$, so there is a strict gap and the simplest dyadic between them is $0$; this word is cold. For $10$, the raw bounds are reversed, so the word is non-cold and keeps stored score $+4$.

After dividing by the common scale, the multiset of scores is therefore

$$\{1,0,1,-1\},$$

and the only cold word has score $0$. Now count ordered triples. Negative totals occur in exactly four patterns:

$$(-1,-1,-1)\quad\text{gives }1,$$

$$(-1,-1,0)\quad\text{gives }3,$$

$$(-1,0,0)\quad\text{gives }3,$$

$$(-1,-1,+1)\quad\text{gives }3\cdot 2=6,$$

because the $+1$ entry can be chosen from two distinct words. Altogether this gives $1+3+3+6=13$ negative triples. The only cold zero-sum triple is $(01,01,01)$, contributing one more case, so

$$G(2,3)=13+1=14,$$

which matches the built-in check used by the C++ implementation.

How the Code Works

Bottom-up evaluation of all binary words

The implementations enumerate all non-empty binary words of lengths $1,2,\dots,n$ level by level. For each final-layer word they inspect every proper suffix length and every proper prefix length, form the two raw bounds, and either collapse the state to one canonical dyadic number or keep the raw endpoints. The C++ version can parallelize the loop over words of a fixed length with OpenMP; the Python and Java versions execute the same recurrence serially.

Building the two score histograms

After the layer of length $n$ is complete, the implementations no longer need the full prefix/suffix structure. They sweep once over the final scores, count how often each score appears, and separately count how often it appears among cold words. This produces the all-words histogram and the cold-only histogram described above.

Repeated convolutions and the final count

Because $k=7$ is small, the implementations build the required convolution powers by repeated hash-map convolution rather than by FFT-style machinery. To count negative totals, one of the two resulting supports is sorted and prefix-summed, so every score from the other side can add all compatible partners with a single binary search. Exact-zero cold totals are even simpler: they are found by matching a score with its negation in the opposite cold distribution.

Complexity Analysis

The dynamic program processes every binary word of length at most $n$, so it visits $(2^{n+1}-2)$ states in total. For each state it scans all proper suffix lengths and all proper prefix lengths, and in the cold case it may search through up to $n$ dyadic scales. This gives overall time $O(n2^n)$ and memory $O(2^n)$ for the recurrence phase.

If $M$ is the largest support size among the intermediate score distributions, each hash-map convolution costs $O(M^2)$ in the naive representation, so the convolution phase is $O(kM^2)$. The negative-total count adds a sorting step $O(M\log M)$. The crucial point is that the algorithm depends on the number of distinct reachable scores, not on the full tuple space $(2^n)^k$.

Footnotes and References

Project Euler problem page: https://projecteuler.net/problem=949
Combinatorial game theory: Wikipedia - Combinatorial game theory
Partisan game: Wikipedia - Partisan game
Dyadic rational: Wikipedia - Dyadic rational
Convolution: Wikipedia - Convolution

Problem 949 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <unordered_map>
#include <utility>
#include <vector>

#ifdef _OPENMP
#include <omp.h>
#endif

using i32 = int32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

static constexpr u64 MOD = 1001001011ULL;

static inline u64 mod_add(u64 a, u64 b, u64 mod) {
    if (mod == 0) {
        return a + b;
    }
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

static inline u64 mod_mul(u64 a, u64 b, u64 mod) {
    if (mod == 0) {
        return a * b;
    }
    return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) % mod);
}

static inline i32 floor_div_pow2(i32 x, int s) {
    if (s == 0) return x;
    if (x >= 0) return static_cast<i32>(x >> s);
    const i32 ax = static_cast<i32>(-x);
    const i32 add = static_cast<i32>((1u << s) - 1u);
    return static_cast<i32>(-((ax + add) >> s));
}

static inline i32 ceil_div_pow2(i32 x, int s) {
    if (s == 0) return x;
    if (x >= 0) return static_cast<i32>((x + static_cast<i32>((1u << s) - 1u)) >> s);
    return static_cast<i32>(-((static_cast<i32>(-x)) >> s));
}

static i32 simplest_between(i32 u, i32 d, int e) {
    for (int m = 0; m <= e; ++m) {
        const int s = e - m;
        const i32 p_min = static_cast<i32>(floor_div_pow2(u, s) + 1);
        const i32 p_max = static_cast<i32>(ceil_div_pow2(d, s) - 1);
        if (p_min > p_max) continue;

        i32 p = 0;
        if (p_min > 0) {
            p = p_min;
        } else if (p_max < 0) {
            p = p_max;
        } else {
            p = 0;
        }

        if (m > 0 && p != 0 && (p & 1) == 0) {
            if (p + 1 <= p_max && ((p + 1) & 1) == 1) {
                ++p;
            } else if (p - 1 >= p_min && ((p - 1) & 1) == 1) {
                --p;
            }
        }

        return static_cast<i32>(static_cast<int64_t>(p) << s);
    }
    return 0;
}

struct UHotResult {
    std::vector<i32> u_full;
    std::vector<uint8_t> is_hot;
};

static UHotResult compute_u_hot(int n) {
    const int e = n;
    const i32 scale = static_cast<i32>(1u << e);
    const int total = static_cast<int>((1u << (n + 1)) - 1u);

    std::vector<i32> dp_u(total);
    std::vector<i32> dp_d(total);

    const int start1 = 1;
    dp_u[start1 + 0] = scale;
    dp_d[start1 + 0] = scale;
    dp_u[start1 + 1] = -scale;
    dp_d[start1 + 1] = -scale;

    std::vector<uint8_t> hot(static_cast<size_t>(1u << n), 0);

    for (int length = 2; length <= n; ++length) {
        const int size = 1u << length;
        const int start = (1u << length) - 1u;
        const bool final_layer = (length == n);

#ifdef _OPENMP
#pragma omp parallel for schedule(static) if (size >= (1 << 15))
#endif
        for (int bits = 0; bits < size; ++bits) {
            i32 u_raw = std::numeric_limits<i32>::min();
            for (int s_len = 1; s_len < length; ++s_len) {
                const int suf = bits & ((1u << s_len) - 1u);
                const int idx = (1u << s_len) - 1u + suf;
                const i32 cand = dp_d[idx];
                if (cand > u_raw) u_raw = cand;
            }

            i32 d_raw = std::numeric_limits<i32>::max();
            for (int p_len = 1; p_len < length; ++p_len) {
                const int pre = bits >> (length - p_len);
                const int idx = (1u << p_len) - 1u + pre;
                const i32 cand = dp_u[idx];
                if (cand < d_raw) d_raw = cand;
            }

            const int idx = start + bits;
            if (u_raw < d_raw) {
                const i32 x = simplest_between(u_raw, d_raw, e);
                dp_u[idx] = x;
                dp_d[idx] = x;
                if (final_layer) hot[static_cast<size_t>(bits)] = 0;
            } else {
                dp_u[idx] = u_raw;
                dp_d[idx] = d_raw;
                if (final_layer) hot[static_cast<size_t>(bits)] = 1;
            }
        }
    }

    const int start_n = (1u << n) - 1u;
    const int full_size = 1u << n;

    UHotResult out;
    out.u_full.assign(dp_u.begin() + start_n, dp_u.begin() + start_n + full_size);
    out.is_hot = std::move(hot);
    return out;
}

using Dist = std::unordered_map<i32, u64>;

static Dist convolve(const Dist& a_in, const Dist& b_in, u64 mod) {
    if (a_in.empty() || b_in.empty()) return {};
    const Dist* a = &a_in;
    const Dist* b = &b_in;
    if (a->size() > b->size()) std::swap(a, b);

    Dist out;
    out.reserve(a->size() * std::min<size_t>(b->size(), 2048));

    for (const auto& [xa, ca] : *a) {
        for (const auto& [xb, cb] : *b) {
            const i32 key = static_cast<i32>(xa + xb);
            const u64 add = mod_mul(ca, cb, mod);
            auto it = out.find(key);
            if (it == out.end()) {
                out.emplace(key, add);
            } else {
                it->second = mod_add(it->second, add, mod);
            }
        }
    }
    return out;
}

static Dist pow_small(const Dist& hist, int t, u64 mod) {
    if (t == 0) return Dist{{0, 1}};
    Dist d = hist;
    for (int i = 1; i < t; ++i) {
        d = convolve(d, hist, mod);
    }
    return d;
}

static u64 count_sum_lt_zero(const Dist& a, const Dist& b, u64 mod) {
    std::vector<std::pair<i32, u64>> b_items;
    b_items.reserve(b.size());
    for (const auto& kv : b) b_items.push_back(kv);
    std::sort(b_items.begin(), b_items.end(),
              [](const auto& x, const auto& y) { return x.first < y.first; });

    std::vector<i32> b_sums;
    b_sums.reserve(b_items.size());
    for (const auto& [s, _] : b_items) b_sums.push_back(s);

    std::vector<u64> pref(b_items.size() + 1, 0);
    for (size_t i = 0; i < b_items.size(); ++i) {
        pref[i + 1] = mod_add(pref[i], b_items[i].second, mod);
    }

    u64 ans = 0;
    for (const auto& [sa, ca] : a) {
        const i32 target = static_cast<i32>(-sa);
        const auto it = std::lower_bound(b_sums.begin(), b_sums.end(), target);
        const size_t idx = static_cast<size_t>(it - b_sums.begin());
        ans = mod_add(ans, mod_mul(ca, pref[idx], mod), mod);
    }
    return ans;
}

static u64 count_sum_eq_zero(const Dist& a_in, const Dist& b_in, u64 mod) {
    const Dist* a = &a_in;
    const Dist* b = &b_in;
    if (a->size() > b->size()) std::swap(a, b);

    u64 ans = 0;
    for (const auto& [s, ca] : *a) {
        auto it = b->find(static_cast<i32>(-s));
        if (it == b->end()) continue;
        ans = mod_add(ans, mod_mul(ca, it->second, mod), mod);
    }
    return ans;
}

static u64 G(int n, int k, u64 mod) {
    if (k <= 0 || (k % 2) == 0) throw std::invalid_argument("k must be positive and odd");
    if (n <= 0) throw std::invalid_argument("n must be positive");

    const auto [u_full, is_hot] = compute_u_hot(n);

    Dist hist_all;
    Dist hist_cold;
    hist_all.reserve(1u << 12);
    hist_cold.reserve(1u << 12);

    for (size_t i = 0; i < u_full.size(); ++i) {
        const i32 v = u_full[i];
        {
            auto it = hist_all.find(v);
            if (it == hist_all.end()) {
                hist_all.emplace(v, (mod == 0) ? 1ULL : 1ULL % mod);
            } else {
                it->second = mod_add(it->second, 1, mod);
            }
        }
        if (is_hot[i] == 0) {
            auto it = hist_cold.find(v);
            if (it == hist_cold.end()) {
                hist_cold.emplace(v, (mod == 0) ? 1ULL : 1ULL % mod);
            } else {
                it->second = mod_add(it->second, 1, mod);
            }
        }
    }

    const int a = k / 2;
    const int b = k - a;

    const Dist dist_a = pow_small(hist_all, a, mod);
    const Dist dist_b = pow_small(hist_all, b, mod);
    const u64 neg = count_sum_lt_zero(dist_a, dist_b, mod);

    const Dist cold_a = pow_small(hist_cold, a, mod);
    const Dist cold_b = pow_small(hist_cold, b, mod);
    const u64 zero_cold = count_sum_eq_zero(cold_a, cold_b, mod);

    return mod_add(neg, zero_cold, mod);
}

int main() {
#ifdef _OPENMP
    std::cout << "OpenMP threads: " << omp_get_max_threads() << "\n";
#endif

    const u64 g23 = G(2, 3, 0);
    std::cout << "G(2,3) = " << g23 << " (expected 14)\n";
    if (g23 != 14) return 1;

    const u64 g43 = G(4, 3, 0);
    std::cout << "G(4,3) = " << g43 << " (expected 496)\n";
    if (g43 != 496) return 1;

    const u64 g85 = G(8, 5, 0);
    std::cout << "G(8,5) = " << g85 << " (expected 26359197010)\n";
    if (g85 != 26359197010ULL) return 1;

    const u64 ans = G(20, 7, MOD);
    std::cout << "G(20,7) mod " << MOD << " = " << ans << "\n";
    return 0;
}

Python

import sys
from collections import defaultdict

sys.setrecursionlimit(2000)

def solve():
    MOD = 1001001011

    def ma(a, b): return (a+b)%MOD
    def mm(a, b): return a*b%MOD

    def fdp2(x, s):
        if s == 0: return x
        if x >= 0: return x >> s
        return -((-x + (1<<s)-1)>>s)

    def cdp2(x, s):
        if s == 0: return x
        if x >= 0: return (x + (1<<s)-1) >> s
        return -((-x)>>s)

    def simplest_between(u, d, e):
        for m in range(e+1):
            s = e - m
            p_min = fdp2(u, s) + 1; p_max = cdp2(d, s) - 1
            if p_min > p_max: continue
            if p_min > 0: p = p_min
            elif p_max < 0: p = p_max
            else: p = 0
            if m > 0 and p != 0 and p%2 == 0:
                if p+1 <= p_max and (p+1)%2 == 1: p += 1
                elif p-1 >= p_min and (p-1)%2 == 1: p -= 1
            return p << s
        return 0

    def compute_u_hot(n):
        e = n; scale = 1 << e; total = (1 << (n+1)) - 1
        dp_u = [0]*total; dp_d = [0]*total
        dp_u[1] = scale; dp_d[1] = scale
        dp_u[2] = -scale; dp_d[2] = -scale
        hot = [0]*(1<<n)
        INF = float('inf')
        for length in range(2, n+1):
            size = 1 << length; start = size - 1
            final = (length == n)
            for bits in range(size):
                u_raw = -INF
                for s_len in range(1, length):
                    suf = bits & ((1<<s_len)-1); idx = (1<<s_len)-1+suf
                    if dp_d[idx] > u_raw: u_raw = dp_d[idx]
                d_raw = INF
                for p_len in range(1, length):
                    pre = bits >> (length-p_len); idx = (1<<p_len)-1+pre
                    if dp_u[idx] < d_raw: d_raw = dp_u[idx]
                idx2 = start + bits
                if u_raw < d_raw:
                    x = simplest_between(u_raw, d_raw, e)
                    dp_u[idx2] = x; dp_d[idx2] = x
                    if final: hot[bits] = 0
                else:
                    dp_u[idx2] = u_raw; dp_d[idx2] = d_raw
                    if final: hot[bits] = 1
        start_n = (1<<n)-1
        u_full = dp_u[start_n:start_n+(1<<n)]
        return u_full, hot

    def conv(a, b):
        out = defaultdict(int)
        for xa, ca in a.items():
            for xb, cb in b.items():
                out[xa+xb] = ma(out[xa+xb], mm(ca, cb))
        return out

    def pow_small(hist, t):
        if t == 0: return {0: 1}
        d = dict(hist)
        for _ in range(1, t): d = conv(d, hist)
        return d

    def count_sum_lt_zero(a, b):
        items = sorted(b.items()); keys = [k for k,_ in items]; vals = [v for _,v in items]
        pref = [0]*(len(vals)+1)
        for i in range(len(vals)): pref[i+1] = ma(pref[i], vals[i])
        from bisect import bisect_left
        ans = 0
        for sa, ca in a.items():
            target = -sa; idx = bisect_left(keys, target)
            ans = ma(ans, mm(ca, pref[idx]))
        return ans

    def count_sum_eq_zero(a, b):
        ans = 0
        if len(a) > len(b): a, b = b, a
        for s, ca in a.items():
            if -s in b: ans = ma(ans, mm(ca, b[-s]))
        return ans

    n = 20; k = 7
    u_full, is_hot = compute_u_hot(n)
    hist_all = defaultdict(int); hist_cold = defaultdict(int)
    for i in range(len(u_full)):
        v = u_full[i]; hist_all[v] = ma(hist_all[v], 1)
        if is_hot[i] == 0: hist_cold[v] = ma(hist_cold[v], 1)

    a2 = k//2; b2 = k - a2
    dist_a = pow_small(hist_all, a2); dist_b = pow_small(hist_all, b2)
    neg = count_sum_lt_zero(dist_a, dist_b)
    cold_a = pow_small(hist_cold, a2); cold_b = pow_small(hist_cold, b2)
    zero_cold = count_sum_eq_zero(cold_a, cold_b)
    return str(ma(neg, zero_cold))

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

Java

import java.util.*;

public class Euler949 {
    static final long MOD = 1001001011;

    public static String solve() {
        int n = 20, k = 7;
        int e = n;
        int total = (1 << (n + 1)) - 1;
        long scale = 1L << e;
        long[] dpU = new long[total], dpD = new long[total];
        dpU[1] = scale;
        dpD[1] = scale;
        dpU[2] = -scale;
        dpD[2] = -scale;
        int[] hot = new int[1 << n];
        long INF = Long.MAX_VALUE / 2;
        for (int length = 2; length <= n; length++) {
            int size = 1 << length;
            int start = size - 1;
            boolean isFinal = (length == n);
            for (int bits = 0; bits < size; bits++) {
                long uRaw = -INF;
                for (int sLen = 1; sLen < length; sLen++) {
                    int suf = bits & ((1 << sLen) - 1);
                    int idx = (1 << sLen) - 1 + suf;
                    if (dpD[idx] > uRaw)
                        uRaw = dpD[idx];
                }
                long dRaw = INF;
                for (int pLen = 1; pLen < length; pLen++) {
                    int pre = bits >> (length - pLen);
                    int idx = (1 << pLen) - 1 + pre;
                    if (dpU[idx] < dRaw)
                        dRaw = dpU[idx];
                }
                int idx2 = start + bits;
                if (uRaw < dRaw) {
                    long x = simplestBetween(uRaw, dRaw, e);
                    dpU[idx2] = x;
                    dpD[idx2] = x;
                    if (isFinal)
                        hot[bits] = 0;
                } else {
                    dpU[idx2] = uRaw;
                    dpD[idx2] = dRaw;
                    if (isFinal)
                        hot[bits] = 1;
                }
            }
        }
        int startN = (1 << n) - 1;
        long[] uFull = new long[1 << n];
        System.arraycopy(dpU, startN, uFull, 0, 1 << n);

        Map<Long, Long> histAll = new HashMap<>(), histCold = new HashMap<>();
        for (int i = 0; i < uFull.length; i++) {
            histAll.merge(uFull[i], 1L, (a, b) -> (a + b) % MOD);
            if (hot[i] == 0)
                histCold.merge(uFull[i], 1L, (a, b) -> (a + b) % MOD);
        }
        int a2 = k / 2, b2 = k - a2;
        Map<Long, Long> distA = powSmall(histAll, a2), distB = powSmall(histAll, b2);
        long neg = countSumLt0(distA, distB);
        Map<Long, Long> coldA = powSmall(histCold, a2), coldB = powSmall(histCold, b2);
        long zeroCold = countSumEq0(coldA, coldB);
        return String.valueOf((neg + zeroCold) % MOD);
    }

    static long simplestBetween(long u, long d, int e) {
        for (int m = 0; m <= e; m++) {
            int s = e - m;
            long pMin = fdp2(u, s) + 1, pMax = cdp2(d, s) - 1;
            if (pMin > pMax)
                continue;
            long p = pMin > 0 ? pMin : (pMax < 0 ? pMax : 0);
            if (m > 0 && p != 0 && p % 2 == 0) {
                if (p + 1 <= pMax && (p + 1) % 2 != 0)
                    p++;
                else if (p - 1 >= pMin && (p - 1) % 2 != 0)
                    p--;
            }
            return p << s;
        }
        return 0;
    }

    static long fdp2(long x, int s) {
        if (s == 0)
            return x;
        if (x >= 0)
            return x >> s;
        return -((-x + (1L << s) - 1) >> s);
    }

    static long cdp2(long x, int s) {
        if (s == 0)
            return x;
        if (x >= 0)
            return (x + (1L << s) - 1) >> s;
        return -((-x) >> s);
    }

    static Map<Long, Long> conv(Map<Long, Long> a, Map<Long, Long> b) {
        Map<Long, Long> out = new HashMap<>();
        for (var ea : a.entrySet())
            for (var eb : b.entrySet())
                out.merge(ea.getKey() + eb.getKey(), ea.getValue() * eb.getValue() % MOD, (x, y) -> (x + y) % MOD);
        return out;
    }

    static Map<Long, Long> powSmall(Map<Long, Long> hist, int t) {
        if (t == 0)
            return Map.of(0L, 1L);
        Map<Long, Long> d = new HashMap<>(hist);
        for (int i = 1; i < t; i++)
            d = conv(d, hist);
        return d;
    }

    static long countSumLt0(Map<Long, Long> a, Map<Long, Long> b) {
        List<Map.Entry<Long, Long>> items = new ArrayList<>(b.entrySet());
        items.sort(Comparator.comparingLong(Map.Entry::getKey));
        long[] keys = new long[items.size()];
        long[] pref = new long[items.size() + 1];
        for (int i = 0; i < items.size(); i++) {
            keys[i] = items.get(i).getKey();
            pref[i + 1] = (pref[i] + items.get(i).getValue()) % MOD;
        }
        long ans = 0;
        for (var ea : a.entrySet()) {
            long target = -ea.getKey();
            int idx = lowerBound(keys, target);
            ans = (ans + ea.getValue() * pref[idx]) % MOD;
        }
        return ans;
    }

    static long countSumEq0(Map<Long, Long> a, Map<Long, Long> b) {
        long ans = 0;
        for (var ea : a.entrySet()) {
            Long v = b.get(-ea.getKey());
            if (v != null)
                ans = (ans + ea.getValue() * v) % MOD;
        }
        return ans;
    }

    static int lowerBound(long[] arr, long target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }

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