import java.util.Arrays;

public class Euler961 {

    static class Solver {
        byte[][] memo;

        Solver() {
            memo = new byte[19][1 << 18];
            for (int i = 0; i < 19; i++) {
                Arrays.fill(memo[i], (byte) -1);
            }
        }

        long WPow10(int exp) {
            long[] pow9 = new long[19];
            pow9[0] = 1L;
            for (int i = 1; i <= 18; ++i) {
                pow9[i] = pow9[i - 1] * 9L;
            }

            long ans = 0L;
            for (int len = 1; len <= exp; ++len) {
                int base = 1 << (len - 1);
                int limit = 1 << (len - 1);
                for (int tail = 0; tail < limit; ++tail) {
                    int mask = base | tail;
                    if (isWinning(mask, len)) {
                        int ones = Integer.bitCount(mask);
                        ans += pow9[ones];
                    }
                }
            }
            return ans;
        }

        boolean isWinning(int mask, int len) {
            if (len == 0) {
                return false;
            }
            if (memo[len][mask] != -1) {
                return memo[len][mask] != 0;
            }

            for (int i = 0; i < len; ++i) {
                int j = len - 1 - i;
                int high = mask >> (j + 1);
                int low = mask & ((1 << j) - 1);
                int nextMask = (high << j) | low;
                int nextLen = len - 1;

                while (nextLen > 0 && ((nextMask >> (nextLen - 1)) & 1) == 0) {
                    --nextLen;
                }

                if (!isWinning(nextMask, nextLen)) {
                    memo[len][mask] = 1;
                    return true;
                }
            }

            memo[len][mask] = 0;
            return false;
        }
    }

    public static String solve() {
        Solver solver = new Solver();
        return Long.toString(solver.WPow10(18));
    }

    public static void main(String[] args) {
        Solver solver = new Solver();
        if (solver.WPow10(2) != 18L || solver.WPow10(4) != 1656L) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}