Problem 209: Circular Logic

Project Euler Problem 209 Solution

EulerSolve provides an optimized solution for Project Euler Problem 209, Circular Logic, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $\tau : \{0,1\}^6 \to \{0,1\}$ be a Boolean truth table on six input bits. The condition in the problem is $$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0,$$ for every 6-bit state $(a,b,c,d,e,f)$. In other words, if we define the state transition $$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$ then no state and its successor under $T$ are both allowed to receive the value 1. The task is to count how many truth tables satisfy this global constraint. The key point is that the transition graph on the 64 states is not an arbitrary functional graph. It is actually a permutation, so the whole graph splits into disjoint directed cycles. Once those cycle lengths are known, the Boolean counting problem becomes a product of independent cycle counts. Mathematical Approach The entire solution is driven by the structure of the six-bit transition. The implementations do not search over truth tables at all; they first decompose the 64 states into cycles, then count admissible 0/1 labelings on each cycle. The six-bit transition is a permutation Write the output of $T$ as $(u,v,w,p,q,r)$. By definition, $$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$ These equations can be inverted immediately: $$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$ So every output state has exactly one predecessor....

Detailed mathematical approach

Problem Summary

A truth table $\tau$ with six inputs assigns an output bit, $0$ or $1$, to each of the $2^6=64$ inputs $(a,b,c,d,e,f)$ of six bits. We must count the tables that satisfy

$$\begin{aligned}&\tau(a,b,c,d,e,f)\wedge{}\\&\tau\bigl(b,c,d,e,f,\,a\oplus(b\wedge c)\bigr)=0\end{aligned}$$

for every input. Here $\wedge$ is AND and $\oplus$ is XOR, the two operations whose truth tables the statement shows: $x\wedge y$ is $1$ only when $x=y=1$, and $x\oplus y$ is $1$ exactly when $x\ne y$. In words: if $\tau$ gives the output $1$ to an input, it must give $0$ to the input obtained by dropping the first bit $a$ and appending the new bit $a\oplus(b\wedge c)$. The statement gives no checkpoint values. ^[1]

The whole solution in one sentence: the drop-and-append rule can be undone, so it arranges the $64$ inputs in closed loops, and since inputs with output $1$ must never be neighbours on a loop, the count is the product, over the loops, of the numbers of such choices, which turn out to be Lucas numbers.

Mathematical Approach

We turn the condition into a statement about a map on the $64$ inputs, try it on three inputs, split the inputs into cycles and count the allowed outputs on each cycle.

1. Inputs as words, and the successor

We write an input as the six-bit word $abcdef$, for example $\mathtt{011000}$ for $(0,1,1,0,0,0)$, and call

$$\begin{aligned}T(a,b,c,d,e,f)&=(b,c,d,e,f,g),\\g&=a\oplus(b\wedge c),\end{aligned}$$

its successor: $T$ shifts the word one place to the left, so that $a$ falls off, and appends the new bit $g$. For example, $T(\mathtt{000011})=\mathtt{000110}$, because $b=c=0$ gives $g=a=0$; $T(\mathtt{011000})=\mathtt{110001}$, because $g=0\oplus1=1$; and $T(\mathtt{111111})=\mathtt{111110}$, because $g=1\oplus1=0$. The condition of the problem says: if $\tau(x)=1$, then $\tau(T(x))=0$. Draw an arrow from every input $x$ to its successor $T(x)$; a table is valid exactly when no arrow joins two inputs with output $1$. A table is a list of $64$ output bits, so there are $2^{64}\approx1.8\cdot10^{19}$ tables, ^[2] far too many to try; we study the arrows instead.

2. A warm-up with three inputs

The same question for three inputs uses the $8$ words of three bits and the rule

$$T(a,b,c)=\bigl(b,c,\,a\oplus(b\wedge c)\bigr).$$

Following the arrows from every word gives three closed loops:

$$\begin{aligned}&\mathtt{000}\to\mathtt{000},\\&\mathtt{001}\to\mathtt{010}\to\mathtt{100}\to\mathtt{001},\\&\mathtt{011}\to\mathtt{111}\to\mathtt{110}\to\mathtt{101}\to\mathtt{011}.\end{aligned}$$

The arrow from $\mathtt{000}$ to itself forces $\tau(\mathtt{000})=0$, because for this input the condition compares $\tau(\mathtt{000})$ with itself. On the loop of three words every two words are joined by an arrow, so at most one of them gets the output $1$: $4$ ways. On the loop of four words the allowed outputs, read along the loop, are $0000$, $1000$, $0100$, $0010$, $0001$, $1010$ and $0101$: $7$ ways. Every arrow stays inside its loop, so the three choices are independent, and the three-input version has $1\cdot4\cdot7=28$ valid tables; a check of all $2^8=256$ tables confirms $28$.

3. The successor can be undone

Suppose we know the successor $(u,v,w,p,q,r)=T(a,b,c,d,e,f)$. Its first five bits are $b,c,d,e,f$, and since $r=a\oplus(b\wedge c)$ and XOR with the same bit twice changes nothing,

$$a=r\oplus(u\wedge v).$$

So every word has exactly one predecessor: $T$ is a bijection, a permutation of the $64$ words. The lone $a$ in the new bit is essential. If the new bit were $b\wedge c$ alone, $\mathtt{000000}$ and $\mathtt{100000}$ would both have the successor $\mathtt{000000}$. In general, shifting left and appending a new bit $h$ gives a permutation exactly when changing $a$ always changes $h$, that is, when $h$ is $a$ XOR a function of the other five bits; otherwise two words that differ only in $a$ have the same successor. Machines of this kind are called feedback shift registers, and those of this form permute their states. ^[3]

4. A permutation splits into cycles

Start at any word $x$ and follow the arrows: $x$, $T(x)$, $T(T(x))$, and so on. There are only $64$ words, so some word appears twice; let $T^j(x)$, the word reached after $j$ steps, be the first repetition, equal to an earlier $T^i(x)$ with $i\lt j$. If $i\gt0$, then $T^{i-1}(x)$ and $T^{j-1}(x)$ would be two different words with the same successor, which Section 3 rules out. So $i=0$: the walk comes back to $x$ itself. Every word therefore lies on exactly one closed loop, called a cycle, different cycles share no words, and a word with $T(x)=x$ is a cycle of length $1$. This is the decomposition of a permutation into disjoint cycles. ^[4]

5. The cycles of the six-bit rule

When $b\wedge c=0$, the new bit is $g=a$, and $T$ simply rotates the word: $abcdef$ becomes $bcdefa$. Now take a word with no two neighbouring $1$s even when it is read around a circle, so that $f$ and $a$ count as neighbours too. Then $b$ and $c$ are not both $1$, so $T$ rotates the word, and the rotated word has the same property. On these words $T$ is the rotation, and their cycles are the rotation classes:

$\mathtt{000000}$, a cycle of length $1$;
$\mathtt{010101}$ and $\mathtt{101010}$, a cycle of length $2$;
the three rotations of $\mathtt{001001}$, a cycle of length $3$;
the six rotations of $\mathtt{000001}$, a cycle of length $6$;
the six rotations of $\mathtt{000101}$, a cycle of length $6$.

These are $1+2+3+6+6=18$ words, and by Section 8 there are exactly $18$ circular six-bit words without neighbouring $1$s, so the list is complete. The word $\mathtt{000000}$ is the only one with $T(x)=x$: that equation makes all six bits equal, say to $v$, and then the new bit $v\oplus(v\wedge v)=0$ must equal $v$. As $T$ is a permutation and sends these $18$ words to one another, it also sends the other $46$ words to one another, and following the arrows shows that they form a single cycle, which begins with $\mathtt{000011}$, $\mathtt{000110}$, $\mathtt{001100}$, $\mathtt{011000}$, $\mathtt{110001}$, $\mathtt{100011}$, $\mathtt{000111}$. So the cycle lengths are $1$, $2$, $3$, $6$, $6$ and $46$. That the other words form a single cycle is a computed fact, not a general law: with seven inputs they split into three cycles.

6. One cycle at a time

Take a cycle $s_0\to s_1\to\cdots\to s_{n-1}\to s_0$ and write $x_i=\tau(s_i)$. The conditions for the inputs $s_0,\ldots,s_{n-1}$ say

$$x_i\wedge x_{i+1}=0\quad(0\le i\le n-1)$$

with $x_n=x_0$: the bits $x_0,\ldots,x_{n-1}$, written around a circle, never have two neighbouring $1$s. Each position stays attached to its input $s_i$, so rotated words count as different choices: on a cycle of length $4$, the words $1000$ and $0100$ give the output $1$ to different inputs. Every condition involves an input and its successor, which lie on the same cycle, so a valid table is any combination of valid choices on the separate cycles. Hence, if $c(n)$ is the number of circular words of $n$ bits without two neighbouring $1$s, the number of valid tables is the product of $c(n)$ over all cycles. For $n=1$ the only condition is $x_0\wedge x_0=0$, so $c(1)=1$; for $n=2$ both conditions say $x_0\wedge x_1=0$, so $c(2)=3$. For $n\ge2$, $c(n)$ is the number of independent sets of a cycle of $n$ vertices, the sets of vertices no two of which are joined by an edge.

7. Words in a row: Fibonacci numbers

First we count words in a row, where only consecutive bits are neighbours and the last bit is not compared with the first. Let $p(m)$ be the number of words of $m$ bits without two neighbouring $1$s. The empty word gives $p(0)=1$, and $p(1)=2$. A longer word either ends in $0$, after any allowed word of $m-1$ bits, or ends in $01$, after any allowed word of $m-2$ bits, so for $m\ge2$

$$p(m)=p(m-1)+p(m-2).$$

This gives $1,2,3,5,8,13,21,\ldots$, the Fibonacci numbers $F_0=0$, $F_1=1$, $F_m=F_{m-1}+F_{m-2}$ shifted by two places: $p(m)=F_{m+2}$. ^[5]

8. Words in a circle: Lucas numbers

Now let $n\ge3$ and split the circular words by their bit $x_0$.

If $x_0=0$, the bits $x_1,\ldots,x_{n-1}$ form an allowed word in a row of $n-1$ bits, because their outer neighbour $x_0$ is $0$ at both ends: $p(n-1)=F_{n+1}$ choices.
If $x_0=1$, both neighbours $x_1$ and $x_{n-1}$ must be $0$, and $x_2,\ldots,x_{n-2}$ form an allowed word in a row of $n-3$ bits: $p(n-3)=F_{n-1}$ choices.

Therefore

$$c(n)=F_{n+1}+F_{n-1}=L_n,$$

the Lucas number $L_n$, defined by $L_0=2$, $L_1=1$ and $L_n=L_{n-1}+L_{n-2}$, with the first values $2,1,3,4,7,11,18,29$. The second equality holds because $F_{n+1}+F_{n-1}$ is $1$ for $n=1$ and $3$ for $n=2$, like $L_1$ and $L_2$, and, as a sum of two Fibonacci sequences, obeys the same recurrence; Lucas numbers are known to count the independent sets of cycles. ^[6] ^[7] By Section 6, $c(1)=1$ and $c(2)=3$, so $c(n)=L_n$ holds for $n=1$ and $n=2$ as well, although the case split above needs $n\ge3$. For example, $c(3)=F_4+F_2=3+1=4$ and $c(4)=5+2=7$ are the counts of the warm-up, and $c(6)=F_7+F_5=13+5=18$: the $13$ circular words with $x_0=0$ and the $5$ with $x_0=1$ are exactly the $18$ words of the five short cycles of Section 5, read with $a$ as $x_0$.

9. A second view: closed walks

A matrix gives the same count for every $n\ge1$ at once. Index the rows and columns of

$$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$$

by the bits $0$ and $1$, so that the entry for $(x,y)$ is $1$ exactly when $x\wedge y=0$. For example, the entry $(0,0)$ of $M^2$ is $2$, for the two allowed walks $0\to0\to0$ and $0\to1\to0$: multiplying by $M$ sums over the bit in the middle. In the same way the entry $(x,y)$ of $M^n$ counts the walks of $n$ steps from $x$ to $y$, ^[8] here the words $x_0x_1\cdots x_n$ with $x_0=x$, $x_n=y$ and no two neighbouring $1$s. So the trace of $M^n$, the sum of its diagonal entries, counts the circular words of Section 6, the cases $n=1$ and $n=2$ included. The formula

$$M^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$$

holds for $n=1$, and multiplying it by $M$ on the right turns its two columns into their sum and the old first column, which by the Fibonacci recurrence is the formula for $n+1$. So the trace is $F_{n+1}+F_{n-1}=L_n$ once more. ^[5] ^[7]

10. The count

Putting Sections 5, 6 and 8 together, the number of valid truth tables is

$$L_1\,L_2\,L_3\,L_6^{\,2}\,L_{46},$$

the product of $1$, $3$, $4$, $18$, $18$ and the $46$-th Lucas number. The warm-up fits the same pattern: its cycles have the lengths $1$, $3$ and $4$, and $L_1L_3L_4=1\cdot4\cdot7=28$.

How the Code Works

All three programs store a word as the integer $x=32a+16b+8c$${}+4d+2e+f$. In the C++ program ^[9] the function next_state reads $a$, $b$ and $c$ as the bits $5$, $4$ and $3$ of $x$ and returns ((x & 31) << 1) | g with g = a ^ (b & c): it keeps the last five bits, shifts them one place to the left and appends $g$, which is $T$ of Section 1. For example, it maps $3$, the word $\mathtt{000011}$, to $6$.

main first calls parse_arguments, which accepts only --skip-checkpoints; for any other argument main returns exit code $1$. Unless that option is given, run_checkpoints requires $c(3)=4$, repeats the cycle search with its own copy of the loop and requires the sorted lengths $1,2,3,6,6,46$, with exit code $2$ on failure. Then main prints the result of solve.

solve finds the cycles of Section 4 with an array visited of $64$ flags. For every start $s=0,1,\ldots,63$ not yet visited, it marks the current word and moves to its successor until it meets a visited word, and it records the number of steps. Because $T$ is a permutation, each walk begins on a cycle with no visited words and stops exactly when it returns to $s$, so this number is the length of the cycle; the walks start at $0$, $1$, $3$, $5$, $9$ and $21$ and find the lengths $1$, $6$, $46$, $6$, $3$ and $2$. Without Section 3, a walk could enter an earlier cycle from outside and record a wrong length. count_cycle_assignments fills a vector with $F_0,\ldots,F_{n+1}$ and returns $F_{n-1}+F_{n+1}=L_n$, as in Section 8; for $n=1$ it reads $F_0=0$ and $F_2=1$. solve multiplies these factors in an unsigned 64-bit integer, as in Section 10.

The Python program defines next_state and count_cycle inside solve, runs the same cycle search on a list of flags and multiplies with its unbounded integers. The Java program does the same in main, nextState and countCycle, with long arithmetic. Neither of them runs checkpoints or reads arguments.

The product fits into 64 bits. From $L_3=4$, $L_4=7$ and, for $n\ge5$, $L_n=L_{n-1}+L_{n-2}$${}\le2^{n-2}+2^{n-3}$ by induction, we get $L_n\le2^{n-1}$ for every $n\ge3$; with $L_1=1$ and $L_2=3\lt2^2$, the product is below $2^{0+2+2+5+5+45}=2^{59}$, within the unsigned 64-bit type of C++ and the signed long of Java. For the seven-input variant the count would have $89$ binary digits, too many for these 64-bit types, while Python's integers would stay exact.

Complexity and Verification

The cycle search makes $64$ successor steps of a few bit operations each, and the C++ checkpoints repeat it once. The Fibonacci vectors take one addition per entry after $F_0$ and $F_1$, $64$ in all because the cycle lengths add up to $64$; the six factors take six more additions and six multiplications. The memory is the $64$ flags, the six lengths and a vector of at most $48$ numbers. For $k$ inputs with $r$ cycles this becomes $2^k$ steps, $2^k+r$ additions and $r$ multiplications, if an operation on a growing number counts as one step, against $2^{2^k}$ tables for a direct search. Here everything finishes instantly.

Besides the C++ checkpoints, the following checks were run for this article; they are not part of the published solutions.

All $64$ successors are different, and the formula of Section 3 undoes $T$ on every word.
Enumerating all $256$ tables with three inputs and all $65536$ with four inputs gives $28$ and $1596$; the four-input rule has cycles of lengths $1$, $2$, $4$ and $9$, and $L_1L_2L_4L_9=1\cdot3\cdot7\cdot76=1596$. An exhaustive search over the $2^{32}$ tables with five inputs, which abandons a partial table as soon as a condition fails, gives $2961596=L_1L_5^{\,2}L_{21}$, for the cycle lengths $1$, $5$, $5$ and $21$ of that rule.
Counting circular words directly confirms $c(n)=L_n$ for every $1\le n\le20$, and the matrix identity of Section 9 holds for every $1\le n\le59$.
A general-purpose counter of independent sets, which branches on one input at a time, splits the rest into connected pieces and remembers its results, knows nothing of cycles or Lucas numbers; on the $64$ inputs and the conditions of the statement it gives the same number as Section 10, and so do the three programs.

Footnotes and References

The references below supply the background facts used above; the cycles of this rule, the reduction to circular words and the checks are derived in this article.

Project Euler 209 — Circular Logic. The official statement defines a k-input binary truth table as a map from k input bits to one output bit, shows the truth tables of AND and XOR, and asks how many 6-input truth tables τ satisfy τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0 for all 6-bit inputs.
Wikipedia — Boolean function. A Boolean function of arity k maps {0, 1}^k to {0, 1}, and there are 2^(2^k) of them, as many as there are different truth tables with k inputs.
R. Arratia, E. R. Canfield and A. W. Hales — Random Feedback Shift Registers, and the Limit Distribution for Largest Cycle Lengths (arXiv:1903.09183). The paper studies binary feedback shift registers linear in the eldest bit, whose state map (x₀, …, xₙ₋₁) ↦ (x₁, …, xₙ₋₁, x₀ ⊕ f(x₁, …, xₙ₋₁)) permutes the 2ⁿ states, and their longest cycles for a random f; this problem is the case n = 6 with the feedback b ∧ c.
Wikipedia — Permutation. A permutation of a finite set decomposes into disjoint cycles, each found by applying the permutation to an element again and again; a fixed point is a cycle of length 1.
Wikipedia — Fibonacci sequence. With F₀ = 0 and F₁ = 1, the number of binary strings of length n without consecutive 1s is Fₙ₊₂, and the n-th power of the matrix with the rows (1, 1) and (1, 0) has the rows (Fₙ₊₁, Fₙ) and (Fₙ, Fₙ₋₁).
Wikipedia — Lucas number. The Lucas numbers 2, 1, 3, 4, 7, 11, 18, 29, … follow the Fibonacci recurrence, satisfy Lₙ = Fₙ₊₁ + Fₙ₋₁, and count the independent vertex sets of the cycle graphs Cₙ of length n ≥ 2.
OEIS A000032 — Lucas numbers. The entry notes that a(n) is the number of independent vertex sets of the cycle graph Cₙ for n ≥ 2, and the trace of the n-th power of the matrix [0, 1; 1, 1], which is M of Section 9 with the two bits in the other order.
Wikipedia — Adjacency matrix. The entry (i, j) of the n-th power of the adjacency matrix of a graph counts the walks of length n from vertex i to vertex j.
C++ — Euler209.cpp. The linked immutable C++ revision contains next_state, count_cycle_assignments, solve and the checks of run_checkpoints. It is the implementation record for this article.

Problem 209 source code

C++

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

namespace {

using u64 = std::uint64_t;

struct Options {
    bool run_checkpoints = true;
};

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

int next_state(const int x) {
    const int a = (x >> 5) & 1;
    const int b = (x >> 4) & 1;
    const int c = (x >> 3) & 1;
    const int g = a ^ (b & c);

    return ((x & 31) << 1) | g;
}

u64 count_cycle_assignments(const int len) {
    // Number of binary circular strings of length len with no adjacent ones:
    // F_{len-1} + F_{len+1}.
    std::vector<u64> fib(static_cast<std::size_t>(len + 2), 0ULL);
    fib[1] = 1ULL;
    for (int i = 2; i <= len + 1; ++i) {
        fib[static_cast<std::size_t>(i)] = fib[static_cast<std::size_t>(i - 1)] + fib[static_cast<std::size_t>(i - 2)];
    }
    return fib[static_cast<std::size_t>(len - 1)] + fib[static_cast<std::size_t>(len + 1)];
}

u64 solve() {
    std::array<std::uint8_t, 64> visited{};
    std::vector<int> cycle_lengths;

    for (int s = 0; s < 64; ++s) {
        if (visited[static_cast<std::size_t>(s)]) {
            continue;
        }
        int len = 0;
        int cur = s;
        while (!visited[static_cast<std::size_t>(cur)]) {
            visited[static_cast<std::size_t>(cur)] = 1;
            cur = next_state(cur);
            ++len;
        }
        cycle_lengths.push_back(len);
    }

    u64 answer = 1ULL;
    for (int len : cycle_lengths) {
        answer *= count_cycle_assignments(len);
    }
    return answer;
}

bool run_checkpoints() {
    if (count_cycle_assignments(3) != 4ULL) {
        std::cerr << "Checkpoint failed for cycle length 3" << '\n';
        return false;
    }

    std::array<std::uint8_t, 64> visited{};
    std::vector<int> lengths;
    for (int s = 0; s < 64; ++s) {
        if (visited[static_cast<std::size_t>(s)]) {
            continue;
        }
        int len = 0;
        int cur = s;
        while (!visited[static_cast<std::size_t>(cur)]) {
            visited[static_cast<std::size_t>(cur)] = 1;
            cur = next_state(cur);
            ++len;
        }
        lengths.push_back(len);
    }
    std::sort(lengths.begin(), lengths.end());
    const std::vector<int> expected = {1, 2, 3, 6, 6, 46};
    if (lengths != expected) {
        std::cerr << "Checkpoint failed for permutation cycle decomposition" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve() << '\n';
    return 0;
}

Python

# Problem 209: Circular Logic
# 6-bit truth table with constraint tau(a,b,c,d,e,f) AND tau(b,c,d,e,f,a XOR (b AND c)) != 1
# The mapping x -> next_state decomposes 64 inputs into cycles.
# For each cycle of length L, count independent sets on a circular graph: F(L-1) + F(L+1).

def solve():
    def next_state(x):
        a = (x >> 5) & 1
        b = (x >> 4) & 1
        c = (x >> 3) & 1
        g = a ^ (b & c)
        return ((x & 31) << 1) | g

    visited = [False] * 64
    cycle_lengths = []
    for s in range(64):
        if visited[s]: continue
        length = 0
        cur = s
        while not visited[cur]:
            visited[cur] = True
            cur = next_state(cur)
            length += 1
        cycle_lengths.append(length)

    def count_cycle(L):
        # Independent sets on cycle of length L = F(L-1) + F(L+1)
        fib = [0] * (L + 2)
        fib[0] = 0
        fib[1] = 1
        for i in range(2, L + 2):
            fib[i] = fib[i-1] + fib[i-2]
        return fib[L-1] + fib[L+1]

    ans = 1
    for L in cycle_lengths:
        ans *= count_cycle(L)
    print(ans)

solve()

Java

public class Euler209 {
    public static void main(String[] args) {
        boolean[] visited = new boolean[64];
        java.util.List<Integer> cycleLengths = new java.util.ArrayList<>();
        for (int s = 0; s < 64; s++) {
            if (visited[s])
                continue;
            int len = 0, cur = s;
            while (!visited[cur]) {
                visited[cur] = true;
                cur = nextState(cur);
                len++;
            }
            cycleLengths.add(len);
        }
        long ans = 1;
        for (int L : cycleLengths)
            ans *= countCycle(L);
        System.out.println(ans);
    }

    static int nextState(int x) {
        int a = (x >> 5) & 1, b = (x >> 4) & 1, c = (x >> 3) & 1;
        int g = a ^ (b & c);
        return ((x & 31) << 1) | g;
    }

    static long countCycle(int L) {
        long[] fib = new long[L + 2];
        fib[1] = 1;
        for (int i = 2; i <= L + 1; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        return fib[L - 1] + fib[L + 1];
    }
}