Problem 774: Conjunctive Sequences

View on Project Euler

Project Euler Problem 774 Solution

EulerSolve provides an optimized solution for Project Euler Problem 774, Conjunctive Sequences, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let \(C(N,B)\) denote the number of sequences \((a_1,\dots,a_N)\) with \(0 \le a_i \le B\) such that every adjacent pair is conjunctive in the bitwise sense: $$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$ The task is to compute this count modulo \(998244353\). A brute-force search would examine \((B+1)^N\) candidates, so the implementations instead perform a memoized binary decomposition of the allowed values. Mathematical Approach The recurrence does not count complete sequences immediately. It counts segments together with boundary obligations that describe what the first and last entries still need to intersect. Step 1: State Definition and Boundary Obligations Define \(D(\ell,B;\lambda,\rho)\) as the number of length-\(\ell\) sequences \((x_1,\dots,x_\ell)\) with \(0 \le x_i \le B\), all internal conjunctions positive, and two extra boundary rules: $$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$ The left state \(\lambda\) constrains \(x_1\), and the right state \(\rho\) constrains \(x_\ell\). There are three kinds of boundary states: $$\top \text{ (no pending constraint)}, \qquad \mathsf{odd} \text{ (the endpoint must be odd)}, \qquad [v] \text{ (the endpoint must share a 1-bit with } v).$$ The marked state \([0]\) is impossible, because no integer can have a positive bitwise conjunction with \(0\)....

Detailed mathematical approach

Problem Summary

Let \(C(N,B)\) denote the number of sequences \((a_1,\dots,a_N)\) with \(0 \le a_i \le B\) such that every adjacent pair is conjunctive in the bitwise sense:

$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$

The task is to compute this count modulo \(998244353\). A brute-force search would examine \((B+1)^N\) candidates, so the implementations instead perform a memoized binary decomposition of the allowed values.

Mathematical Approach

The recurrence does not count complete sequences immediately. It counts segments together with boundary obligations that describe what the first and last entries still need to intersect.

Step 1: State Definition and Boundary Obligations

Define \(D(\ell,B;\lambda,\rho)\) as the number of length-\(\ell\) sequences \((x_1,\dots,x_\ell)\) with \(0 \le x_i \le B\), all internal conjunctions positive, and two extra boundary rules:

$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$

The left state \(\lambda\) constrains \(x_1\), and the right state \(\rho\) constrains \(x_\ell\). There are three kinds of boundary states:

$$\top \text{ (no pending constraint)}, \qquad \mathsf{odd} \text{ (the endpoint must be odd)}, \qquad [v] \text{ (the endpoint must share a 1-bit with } v).$$

The marked state \([0]\) is impossible, because no integer can have a positive bitwise conjunction with \(0\). The final answer is simply

$$C(N,B)=D(N,B;\top,\top).$$

Small bounds are handled directly. When \(B=0\), the only available value is \(0\), so only the trivial length-\(0\) or length-\(1\) unconstrained situation survives. When \(B=1\), every endpoint condition can be checked by explicit enumeration of the values \(0\) and \(1\).

Step 2: Strip Off the Lowest Bit

Every number is either even, \(2y\), or odd, \(2y+1\). This lets us move from the bound \(B\) to roughly half the size. The only subtlety is how a boundary condition changes after fixing the parity of an endpoint.

If the endpoint is forced to be even, write its reduced boundary state as \(\Phi_0(\sigma)\); if it is forced to be odd, write \(\Phi_1(\sigma)\). The rules are

$$\Phi_0(\top)=\top,\qquad \Phi_1(\top)=\top,$$

$$\Phi_0(\mathsf{odd})=[0],\qquad \Phi_1(\mathsf{odd})=\top,$$

$$\Phi_0([v])=[\lfloor v/2 \rfloor],\qquad \Phi_1([v])= \begin{cases} \top, & v \text{ odd},\\ [v/2], & v \text{ even}. \end{cases}$$

These identities come straight from bitwise arithmetic. For example, if an endpoint must intersect \(v\) and the endpoint is odd, then the conjunction is already positive when \(v\) is odd, because the least significant bit is shared automatically.

Step 3: Stable Parity Patterns and Fibonacci Weights

Now let

$$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$$

Suppose first that, when we read the sequence from left to right, no adjacent pair is simultaneously odd. Then every internal edge still depends on higher bits, so after removing the lowest bit from every entry we obtain another segment of the same length at the smaller bound \(m\).

The only thing that remains is to count parity patterns of length \(\ell\) with no consecutive odd entries and prescribed first and last parity. Those counts are Fibonacci numbers. If \((F_k)\) is given by

$$F_0=0,\qquad F_1=1,\qquad F_{k}=F_{k-1}+F_{k-2},$$

and extended to negative indices by

$$F_{-q}=(-1)^{q+1}F_q,$$

then the stable contribution is

$$\begin{aligned} D(\ell,m;\Phi_0(\lambda),\Phi_0(\rho))\,F_\ell &+D(\ell,m;\Phi_0(\lambda),\Phi_1(\rho))\,F_{\ell-1}\\ &+D(\ell,m;\Phi_1(\lambda),\Phi_0(\rho))\,F_{\ell-1}\\ &+D(\ell,m;\Phi_1(\lambda),\Phi_1(\rho))\,F_{\ell-2}. \end{aligned}$$

The coefficients match the four possibilities for the first and last parity: even-even, even-odd, odd-even, and odd-odd.

Step 4: Split at the First Odd-Odd Pair

If a neighboring pair is odd-odd, then its conjunction is already positive at the lowest bit. That edge needs no further higher-bit verification, so the sequence can be cut there into two independent pieces.

If the first such cut happens between positions \(x\) and \(x+1\), the left block ends with an odd value and the right block begins with an odd value. This yields the additional sum

$$\sum_{x=1}^{\ell-1} D(\ell-x,B;\mathsf{odd},\rho)\left( D(x,m;\Phi_1(\lambda),\top)\,F_{x-2} \begin{cases} +D(x,m;\Phi_0(\lambda),\top)\,F_{x-1}, & x \gt 1,\\ 0, & x=1. \end{cases} \right).$$

The right factor counts parity patterns in the prefix that end with an odd element and contain no earlier odd-odd cut. The left factor counts the suffix whose first element is forced to be odd.

Step 5: The Exceptional Top Value When \(B\) Is Even

When \(B\) is even, the value \(B\) itself has no representative inside the common reduced range \(0,\dots,m\), because \(B=2(m+1)\). Therefore sequences containing the value \(B\) must be added separately.

There are three placements to consider:

First, \(B\) may appear inside the sequence and split it into a prefix and a suffix. The suffix then begins with the obligation “intersect \(B\)”, while the prefix ends with the reduced obligation “intersect \(B/2\)”.

Second, \(B\) may sit at the far left, consuming one position and turning the remaining left boundary rule into “must intersect \(B\)”.

Third, \(B\) may sit at the far right, which after reduction produces one more Fibonacci-weighted boundary term. These are exactly the extra terms that appear only in the even-\(B\) branch of the implementations.

Worked Example: \(C(3,4)=18\)

For the small checkpoint \(N=3\) and \(B=4\), the allowed values are \(0,1,2,3,4\). The number \(0\) never appears in a valid sequence, because it has zero conjunction with every neighbor.

Classify by the middle term:

If the middle term is \(1\), then both neighbors must share bit \(1\), so each neighbor is in \(\{1,3\}\), giving \(2^2=4\) sequences.

If the middle term is \(2\), both neighbors must contain bit \(2\), so each neighbor is in \(\{2,3\}\), again giving \(4\) sequences.

If the middle term is \(3\), then a neighbor may be \(1\), \(2\), or \(3\), so we get \(3^2=9\) sequences.

If the middle term is \(4\), then both neighbors must be \(4\), so there is only \(1\) sequence.

Therefore

$$4+4+9+1=18,$$

which matches the checkpoint produced by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They precompute Fibonacci numbers modulo \(998244353\) up to the required sequence length and use the sign rule for negative indices so that the recurrence stays uniform even at short lengths.

After that, the implementation memoizes the state \(D(\ell,B;\lambda,\rho)\). Every time a state is requested, it first discards impossible boundary obligations, then handles the explicit small-\(B\) cases, and finally applies the three recurrence blocks above: the stable no-cut part, the sum over the first odd-odd split, and the special insertion terms when \(B\) is even.

Because identical subproblems occur constantly, memoization is essential. Without it the recursion tree would explode; with it, each distinct state is evaluated once and then reused.

Complexity Analysis

Let \(|\mathcal S|\) be the number of distinct memoized states that actually occur. Each state performs \(O(\ell)\) arithmetic because it may scan all split points \(x=1,\dots,\ell-1\), and in the even-\(B\) branch it performs one more loop of the same order. Hence the total running time is approximately \(O(|\mathcal S| \cdot N)\), with \(O(|\mathcal S|)\) memory for the memo table. The Fibonacci precomputation itself is only \(O(N)\).

Footnotes and References

  1. Problem page: https://projecteuler.net/problem=774
  2. Bitwise operation: Wikipedia — Bitwise operation
  3. Dynamic programming: Wikipedia — Dynamic programming
  4. Fibonacci number: Wikipedia — Fibonacci number
  5. Memoization: Wikipedia — Memoization

Problem 774 source code

C++

#include <cassert>
#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <vector>

namespace {

constexpr int MOD = 998244353;

inline int add_mod(int a, int b) {
    int s = a + b;
    if (s >= MOD) s -= MOD;
    return s;
}

inline int sub_mod(int a, int b) {
    int s = a - b;
    if (s < 0) s += MOD;
    return s;
}

inline int mul_mod(long long a, long long b) {
    return static_cast<int>((static_cast<__int128>(a) * b) % MOD);
}

enum class EdgeType : std::uint8_t { G = 0, O = 1, C = 2 };

struct Edge {
    EdgeType t{EdgeType::G};
    int v{0};
};

inline Edge G() { return Edge{EdgeType::G, 0}; }
inline Edge O() { return Edge{EdgeType::O, 0}; }
inline Edge C(int n) { return Edge{EdgeType::C, n}; }

inline bool is_g(const Edge& e) { return e.t == EdgeType::G; }
inline bool is_o(const Edge& e) { return e.t == EdgeType::O; }
inline bool is_c(const Edge& e) { return e.t == EdgeType::C; }

Edge insert_edge(int n, const Edge& e) {
    if (is_g(e)) return C(n);
    if (is_o(e)) return (n & 1) ? C(n) : C(0);
    assert((e.v & n) > 0);
    return C(n);
}

Edge up0(const Edge& e) {
    if (is_c(e)) return C(e.v / 2);
    if (is_o(e)) return C(0);
    return G();
}

Edge up1(const Edge& e) {
    if (is_c(e)) {
        if ((e.v & 1) == 0) return C(e.v / 2);
        return G();
    }
    return G();
}

struct Key {
    int l;
    int n;
    int left_code;
    int right_code;

    bool operator==(const Key& other) const noexcept {
        return l == other.l && n == other.n && left_code == other.left_code &&
               right_code == other.right_code;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& k) const noexcept {
        std::size_t h = std::hash<int>{}(k.l);
        auto mix = [&](int x) {
            std::size_t v = std::hash<int>{}(x);
            h ^= v + 0x9e3779b97f4a7c15ULL + (h << 6U) + (h >> 2U);
        };
        mix(k.n);
        mix(k.left_code);
        mix(k.right_code);
        return h;
    }
};

int edge_code(const Edge& e) {
    if (is_g(e)) return -1;
    if (is_o(e)) return -2;
    return e.v;
}

class Solver774 {
  public:
    Solver774(int max_l, int a, int b) : a_(a), b_(b) {
        fib_pos_.assign(max_l + 2, 0);
        fib_pos_[0] = 0;
        fib_pos_[1] = 1;
        for (int i = 2; i < static_cast<int>(fib_pos_.size()); ++i) {
            fib_pos_[i] = add_mod(fib_pos_[i - 1], fib_pos_[i - 2]);
        }
        memo_.reserve(1 << 20U);
    }

    int solve() { return f(a_, b_, G(), G()); }

  private:
    int a_;
    int b_;
    std::vector<int> fib_pos_;
    std::unordered_map<Key, int, KeyHash> memo_;

    int fib(int x) const {
        if (x >= 0) return fib_pos_[static_cast<std::size_t>(x)];
        int n = -x;
        int v = fib_pos_[static_cast<std::size_t>(n)];
        if ((n & 1) == 0 && v != 0) v = MOD - v;
        return v;
    }

    int f(int l, int n, const Edge& left, const Edge& right) {
        if ((is_c(left) && left.v == 0) || (is_c(right) && right.v == 0)) return 0;

        const Key key{l, n, edge_code(left), edge_code(right)};
        auto it = memo_.find(key);
        if (it != memo_.end()) return it->second;

        int ret = 0;

        if (n == 0) {
            ret = (l <= 1 && is_g(left) && is_g(right)) ? 1 : 0;
            memo_.emplace(key, ret);
            return ret;
        }

        if (n == 1) {
            if (is_g(left) && is_g(right)) {
                ret = (l > 1) ? 1 : 2;
            } else if ((is_o(left) && is_o(right)) || (is_o(left) && is_g(right)) ||
                       (is_g(left) && is_o(right))) {
                ret = 1;
            } else if (is_c(left) && is_c(right)) {
                ret = ((left.v & 1) && (right.v & 1)) ? 1 : 0;
            } else if (is_c(left)) {
                ret = (left.v & 1) ? 1 : 0;
            } else if (is_c(right)) {
                ret = (right.v & 1) ? 1 : 0;
            } else {
                ret = 0;
            }
            memo_.emplace(key, ret);
            return ret;
        }

        const int m = (n - 1) / 2;

        if (l == 1) {
            if (is_g(left) && is_g(right)) {
                ret = (n + 1) % MOD;
            } else {
                ret = add_mod(f(1, n / 2, up0(left), up0(right)),
                              f(1, m, up1(left), up1(right)));
            }
            memo_.emplace(key, ret);
            return ret;
        }

        int s = 0;
        s = add_mod(s, mul_mod(f(l, m, up0(left), up0(right)), fib(l)));
        s = add_mod(s, mul_mod(f(l, m, up0(left), up1(right)), fib(l - 1)));
        s = add_mod(s, mul_mod(f(l, m, up1(left), up0(right)), fib(l - 1)));
        s = add_mod(s, mul_mod(f(l, m, up1(left), up1(right)), fib(l - 2)));

        const Edge up1o = up1(O());
        for (int x = 1; x <= l - 1; ++x) {
            int right_part = f(l - x, n, O(), right);
            if (x > 1) {
                int left_part = f(x, m, up0(left), up1o);
                s = add_mod(s, mul_mod(mul_mod(left_part, right_part), fib(x - 1)));
            }
            int left_part2 = f(x, m, up1(left), up1o);
            s = add_mod(s, mul_mod(mul_mod(left_part2, right_part), fib(x - 2)));
        }

        if ((n & 1) == 0) {
            const Edge cn = C(n);
            const Edge up0cn = up0(cn);

            for (int x = 2; x <= l - 1; ++x) {
                int right_part = f(l - x, n, cn, right);

                int a = f(x - 1, m, up0(left), up0cn);
                s = add_mod(s, mul_mod(mul_mod(a, right_part), fib(x)));

                int b = f(x - 1, m, up1(left), up0cn);
                s = add_mod(s, mul_mod(mul_mod(b, right_part), fib(x - 1)));
            }

            s = add_mod(s, f(l - 1, n, insert_edge(n, left), right));

            const Edge ins_right = insert_edge(n, right);
            s = add_mod(s, mul_mod(f(l - 1, m, up0(left), up0(ins_right)), fib(l)));
            s = add_mod(s, mul_mod(f(l - 1, m, up1(left), up0(ins_right)), fib(l - 1)));
        }

        ret = s;
        memo_.emplace(key, ret);
        return ret;
    }
};

int compute_c(int n, int b) {
    Solver774 solver(n, n, b);
    return solver.solve();
}

}  // namespace

int main() {
    struct Check {
        int n;
        std::uint64_t b;
        int expected;
    };

    const Check checks[] = {
        {3, 4, 18},
        {10, 6, 2496120},
        {100, 200, 268159379},
    };

    for (const auto& chk : checks) {
        int got = compute_c(chk.n, static_cast<int>(chk.b));
        if (got != chk.expected) {
            std::cerr << "Validation failure: c(" << chk.n << ", " << chk.b
                      << ") = " << got << ", expected " << chk.expected << '\n';
            return 1;
        }
    }

    std::cout << compute_c(123, 123456789) << '\n';
    return 0;
}

Python

import sys

# Increase recursion depth just in case
sys.setrecursionlimit(20000)

MOD = 998244353

def add_mod(a, b):
    s = a + b
    if s >= MOD: s -= MOD
    return s

def mul_mod(a, b):
    return (a * b) % MOD

# EdgeTypes: 0=G, 1=O, 2=C
def is_g(e): return e[0] == 0
def is_o(e): return e[0] == 1
def is_c(e): return e[0] == 2

def G(): return (0, 0)
def O(): return (1, 0)
def C(n): return (2, n)

def insert_edge(n, e):
    if is_g(e): return C(n)
    if is_o(e): return C(n) if (n & 1) else C(0)
    return C(n)

def up0(e):
    if is_c(e): return C(e[1] // 2)
    if is_o(e): return C(0)
    return G()

def up1(e):
    if is_c(e):
        if (e[1] & 1) == 0: return C(e[1] // 2)
        return G()
    return G()

def edge_code(e):
    if is_g(e): return -1
    if is_o(e): return -2
    return e[1]

class Solver774:
    def __init__(self, max_l, a, b):
        self.a_ = a
        self.b_ = b
        self.fib_pos_ = [0] * (max_l + 2)
        self.fib_pos_[0] = 0
        self.fib_pos_[1] = 1
        for i in range(2, max_l + 2):
            self.fib_pos_[i] = add_mod(self.fib_pos_[i - 1], self.fib_pos_[i - 2])
        self.memo_ = {}

    def fib(self, x):
        if x >= 0: return self.fib_pos_[x]
        n = -x
        v = self.fib_pos_[n]
        if (n & 1) == 0 and v != 0: v = MOD - v
        return v

    def f(self, l, n, left, right):
        if (is_c(left) and left[1] == 0) or (is_c(right) and right[1] == 0):
            return 0

        key = (l, n, edge_code(left), edge_code(right))
        if key in self.memo_:
            return self.memo_[key]

        ret = 0

        if n == 0:
            ret = 1 if (l <= 1 and is_g(left) and is_g(right)) else 0
            self.memo_[key] = ret
            return ret

        if n == 1:
            if is_g(left) and is_g(right):
                ret = 1 if (l > 1) else 2
            elif (is_o(left) and is_o(right)) or (is_o(left) and is_g(right)) or (is_g(left) and is_o(right)):
                ret = 1
            elif is_c(left) and is_c(right):
                ret = 1 if ((left[1] & 1) and (right[1] & 1)) else 0
            elif is_c(left):
                ret = 1 if (left[1] & 1) else 0
            elif is_c(right):
                ret = 1 if (right[1] & 1) else 0
            else:
                ret = 0
            self.memo_[key] = ret
            return ret

        m = (n - 1) // 2

        if l == 1:
            if is_g(left) and is_g(right):
                ret = (n + 1) % MOD
            else:
                ret = add_mod(self.f(1, n // 2, up0(left), up0(right)),
                              self.f(1, m, up1(left), up1(right)))
            self.memo_[key] = ret
            return ret

        s = 0
        s = add_mod(s, mul_mod(self.f(l, m, up0(left), up0(right)), self.fib(l)))
        s = add_mod(s, mul_mod(self.f(l, m, up0(left), up1(right)), self.fib(l - 1)))
        s = add_mod(s, mul_mod(self.f(l, m, up1(left), up0(right)), self.fib(l - 1)))
        s = add_mod(s, mul_mod(self.f(l, m, up1(left), up1(right)), self.fib(l - 2)))

        up1o = up1(O())
        for x in range(1, l):
            right_part = self.f(l - x, n, O(), right)
            if x > 1:
                left_part = self.f(x, m, up0(left), up1o)
                s = add_mod(s, mul_mod(mul_mod(left_part, right_part), self.fib(x - 1)))
            left_part2 = self.f(x, m, up1(left), up1o)
            s = add_mod(s, mul_mod(mul_mod(left_part2, right_part), self.fib(x - 2)))

        if (n & 1) == 0:
            cn = C(n)
            up0cn = up0(cn)

            for x in range(2, l):
                right_part = self.f(l - x, n, cn, right)

                a = self.f(x - 1, m, up0(left), up0cn)
                s = add_mod(s, mul_mod(mul_mod(a, right_part), self.fib(x)))

                b = self.f(x - 1, m, up1(left), up0cn)
                s = add_mod(s, mul_mod(mul_mod(b, right_part), self.fib(x - 1)))

            s = add_mod(s, self.f(l - 1, n, insert_edge(n, left), right))

            ins_right = insert_edge(n, right)
            s = add_mod(s, mul_mod(self.f(l - 1, m, up0(left), up0(ins_right)), self.fib(l)))
            s = add_mod(s, mul_mod(self.f(l - 1, m, up1(left), up0(ins_right)), self.fib(l - 1)))

        ret = s
        self.memo_[key] = ret
        return ret

    def solve(self):
        return self.f(self.a_, self.b_, G(), G())

def compute_c(n, b):
    solver = Solver774(n, n, b)
    return solver.solve()

def solve():
    return str(compute_c(123, 123456789))

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

Java

import java.util.HashMap;

public class Euler774 {

    static final int MOD = 998244353;

    static int addMod(int a, int b) {
        int s = a + b;
        if (s >= MOD)
            s -= MOD;
        return s;
    }

    static int subMod(int a, int b) {
        int s = a - b;
        if (s < 0)
            s += MOD;
        return s;
    }

    static int mulMod(long a, long b) {
        return (int) ((a * b) % MOD);
    }

    static final int TYPE_G = 0;
    static final int TYPE_O = 1;
    static final int TYPE_C = 2;

    static class Edge {
        int t;
        int v;

        Edge(int t, int v) {
            this.t = t;
            this.v = v;
        }
    }

    static Edge G() {
        return new Edge(TYPE_G, 0);
    }

    static Edge O() {
        return new Edge(TYPE_O, 0);
    }

    static Edge C(int n) {
        return new Edge(TYPE_C, n);
    }

    static boolean isG(Edge e) {
        return e.t == TYPE_G;
    }

    static boolean isO(Edge e) {
        return e.t == TYPE_O;
    }

    static boolean isC(Edge e) {
        return e.t == TYPE_C;
    }

    static Edge insertEdge(int n, Edge e) {
        if (isG(e))
            return C(n);
        if (isO(e))
            return (n & 1) != 0 ? C(n) : C(0);
        return C(n);
    }

    static Edge up0(Edge e) {
        if (isC(e))
            return C(e.v / 2);
        if (isO(e))
            return C(0);
        return G();
    }

    static Edge up1(Edge e) {
        if (isC(e)) {
            if ((e.v & 1) == 0)
                return C(e.v / 2);
            return G();
        }
        return G();
    }

    static int edgeCode(Edge e) {
        if (isG(e))
            return -1;
        if (isO(e))
            return -2;
        return e.v;
    }

    static class Key {
        int l, n, leftCode, rightCode;

        Key(int l, int n, int leftCode, int rightCode) {
            this.l = l;
            this.n = n;
            this.leftCode = leftCode;
            this.rightCode = rightCode;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof Key))
                return false;
            Key key = (Key) o;
            return l == key.l && n == key.n && leftCode == key.leftCode && rightCode == key.rightCode;
        }

        @Override
        public int hashCode() {
            int h = Integer.hashCode(l);
            h ^= Integer.hashCode(n) + 0x9e3779b9 + (h << 6) + (h >> 2);
            h ^= Integer.hashCode(leftCode) + 0x9e3779b9 + (h << 6) + (h >> 2);
            h ^= Integer.hashCode(rightCode) + 0x9e3779b9 + (h << 6) + (h >> 2);
            return h;
        }
    }

    static class Solver774 {
        int a, b;
        int[] fibPos;
        HashMap<Key, Integer> memo;

        Solver774(int maxL, int a, int b) {
            this.a = a;
            this.b = b;
            fibPos = new int[maxL + 2];
            fibPos[0] = 0;
            fibPos[1] = 1;
            for (int i = 2; i < fibPos.length; i++) {
                fibPos[i] = addMod(fibPos[i - 1], fibPos[i - 2]);
            }
            memo = new HashMap<>();
        }

        int fib(int x) {
            if (x >= 0)
                return fibPos[x];
            int n = -x;
            int v = fibPos[n];
            if ((n & 1) == 0 && v != 0)
                v = MOD - v;
            return v;
        }

        int f(int l, int n, Edge left, Edge right) {
            if ((isC(left) && left.v == 0) || (isC(right) && right.v == 0))
                return 0;

            Key key = new Key(l, n, edgeCode(left), edgeCode(right));
            Integer cached = memo.get(key);
            if (cached != null)
                return cached;

            int ret = 0;

            if (n == 0) {
                ret = (l <= 1 && isG(left) && isG(right)) ? 1 : 0;
                memo.put(key, ret);
                return ret;
            }

            if (n == 1) {
                if (isG(left) && isG(right)) {
                    ret = (l > 1) ? 1 : 2;
                } else if ((isO(left) && isO(right)) || (isO(left) && isG(right)) ||
                        (isG(left) && isO(right))) {
                    ret = 1;
                } else if (isC(left) && isC(right)) {
                    ret = ((left.v & 1) != 0 && (right.v & 1) != 0) ? 1 : 0;
                } else if (isC(left)) {
                    ret = (left.v & 1) != 0 ? 1 : 0;
                } else if (isC(right)) {
                    ret = (right.v & 1) != 0 ? 1 : 0;
                } else {
                    ret = 0;
                }
                memo.put(key, ret);
                return ret;
            }

            int m = (n - 1) / 2;

            if (l == 1) {
                if (isG(left) && isG(right)) {
                    ret = (n + 1) % MOD;
                } else {
                    ret = addMod(f(1, n / 2, up0(left), up0(right)),
                            f(1, m, up1(left), up1(right)));
                }
                memo.put(key, ret);
                return ret;
            }

            int s = 0;
            s = addMod(s, mulMod(f(l, m, up0(left), up0(right)), fib(l)));
            s = addMod(s, mulMod(f(l, m, up0(left), up1(right)), fib(l - 1)));
            s = addMod(s, mulMod(f(l, m, up1(left), up0(right)), fib(l - 1)));
            s = addMod(s, mulMod(f(l, m, up1(left), up1(right)), fib(l - 2)));

            Edge up1o = up1(O());
            for (int x = 1; x <= l - 1; ++x) {
                int rightPart = f(l - x, n, O(), right);
                if (x > 1) {
                    int leftPart = f(x, m, up0(left), up1o);
                    s = addMod(s, mulMod(mulMod(leftPart, rightPart), fib(x - 1)));
                }
                int leftPart2 = f(x, m, up1(left), up1o);
                s = addMod(s, mulMod(mulMod(leftPart2, rightPart), fib(x - 2)));
            }

            if ((n & 1) == 0) {
                Edge cn = C(n);
                Edge up0cn = up0(cn);

                for (int x = 2; x <= l - 1; ++x) {
                    int rightPart = f(l - x, n, cn, right);

                    int a_part = f(x - 1, m, up0(left), up0cn);
                    s = addMod(s, mulMod(mulMod(a_part, rightPart), fib(x)));

                    int b_part = f(x - 1, m, up1(left), up0cn);
                    s = addMod(s, mulMod(mulMod(b_part, rightPart), fib(x - 1)));
                }

                s = addMod(s, f(l - 1, n, insertEdge(n, left), right));

                Edge insRight = insertEdge(n, right);
                s = addMod(s, mulMod(f(l - 1, m, up0(left), up0(insRight)), fib(l)));
                s = addMod(s, mulMod(f(l - 1, m, up1(left), up0(insRight)), fib(l - 1)));
            }

            ret = s;
            memo.put(key, ret);
            return ret;
        }

        int solve() {
            return f(a, b, G(), G());
        }
    }

    static int computeC(int n, int b) {
        Solver774 solver = new Solver774(n, n, b);
        return solver.solve();
    }

    public static String solve() {
        return Integer.toString(computeC(123, 123456789));
    }

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