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());
    }
}