#include <iostream>
const int MOD = (1 << 30) + 1;
template <bool, typename T1, typename T2> struct myIf;
template <typename T1, typename T2>
struct myIf <true, T1, T2>
{
    typedef T1 result;
};
template <typename T1, typename T2>
struct myIf <false, T1, T2>
{
    typedef T2 result;
};
template <int, int, int> struct dp;
template <int cur_mask, int n, int m, int mask> struct metaFor
{
    enum {cur1 = cur_mask | mask, cur2 = (cur_mask & mask) ^ ((1 << n) - 1)};
    typedef typename myIf <((cur1 | (cur1 << 1) | 1) & ((1 << n) - 1)) == (1 << n) - 1 &&
    ((cur2 | (cur2 << 1) | 1) & ((1 << n) - 1)) == (1 << n) - 1,
        dp <n, m - 1, cur_mask>,
        metaFor <-1, n, m, mask>
    >::result add;
    enum {ans = (metaFor <cur_mask - 1, n, m, mask>::ans * 1ll + add::ans) % MOD};
};
template <int n, int m, int mask>
struct metaFor <-1, n, m, mask>
{
    enum {ans = 0};
};
template <int n, int m, int mask> struct dp
{
    enum {ans = metaFor <(1 << n) - 1, n, m, mask>::ans};
};
template <int n, int mask>
struct dp <n, 1, mask>
{
    enum {ans = 1};
};
int main()
{
    enum {n = 6, m = 6};
    enum {mask = 1 << ((n + 1) / 2)};
    std::cout << dp <n, m + 1, (mask * mask - 1) / 3>::ans;
    return 0;
}