import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Euler703 {
    static final long kMod = 1001001011L;

    public static String solve() {
        int n = 20;
        int N = 1 << n;

        int[] succ = new int[N];
        for (int x = 0; x < N; ++x) {
            int b1 = x & 1;
            int b2 = (x >> 1) & 1;
            int b3 = (x >> 2) & 1;
            int last = b1 & (b2 ^ b3);
            succ[x] = (x >> 1) | (last << (n - 1));
        }

        int[] head = new int[N];
        Arrays.fill(head, -1);
        int[] to = new int[N];
        int[] nextEdge = new int[N];

        for (int v = 0; v < N; ++v) {
            int u = succ[v];
            to[v] = v;
            nextEdge[v] = head[u];
            head[u] = v;
        }

        byte[] color = new byte[N];
        int[] pos = new int[N];
        Arrays.fill(pos, -1);
        byte[] inCycle = new byte[N];

        List<int[]> cycles = new ArrayList<>(N / 4);
        int[] path = new int[256];
        int pathLen = 0;

        for (int start = 0; start < N; ++start) {
            if (color[start] != 0) {
                continue;
            }

            pathLen = 0;
            int v = start;
            while (color[v] == 0) {
                color[v] = 1;
                pos[v] = pathLen;
                if (pathLen == path.length) {
                    path = Arrays.copyOf(path, path.length * 2);
                }
                path[pathLen++] = v;
                v = succ[v];
            }

            if (color[v] == 1) {
                int cycleStart = pos[v];
                int[] cyc = new int[pathLen - cycleStart];
                for (int i = cycleStart; i < pathLen; ++i) {
                    int node = path[i];
                    inCycle[node] = 1;
                    cyc[i - cycleStart] = node;
                }
                cycles.add(cyc);
            }

            for (int i = 0; i < pathLen; i++) {
                int node = path[i];
                color[node] = 2;
                pos[node] = -1;
            }
        }

        long[] dp0 = new long[N];
        long[] dp1 = new long[N];
        byte[] done = new byte[N];

        long answer = 1;

        int[] st = new int[N];
        boolean[] expanded = new boolean[N];

        for (int[] cyc : cycles) {
            int m = cyc.length;
            long[] w0 = new long[m];
            long[] w1 = new long[m];
            Arrays.fill(w0, 1L);
            Arrays.fill(w1, 1L);

            for (int i = 0; i < m; ++i) {
                int startU = cyc[i];
                long a0 = 1;
                long a1 = 1;

                for (int e = head[startU]; e != -1; e = nextEdge[e]) {
                    int childVec = to[e];
                    if (inCycle[childVec] != 0)
                        continue;

                    if (done[childVec] == 0) {
                        int stPtr = 0;
                        st[stPtr] = childVec;
                        expanded[stPtr] = false;
                        stPtr++;

                        while (stPtr > 0) {
                            stPtr--;
                            int u = st[stPtr];
                            boolean exp = expanded[stPtr];

                            if (!exp) {
                                st[stPtr] = u;
                                expanded[stPtr] = true;
                                stPtr++;
                                for (int ce = head[u]; ce != -1; ce = nextEdge[ce]) {
                                    int ch = to[ce];
                                    if (inCycle[ch] == 0 && done[ch] == 0) {
                                        st[stPtr] = ch;
                                        expanded[stPtr] = false;
                                        stPtr++;
                                    }
                                }
                            } else {
                                long ways0 = 1;
                                long ways1 = 1;
                                for (int ce = head[u]; ce != -1; ce = nextEdge[ce]) {
                                    int ch = to[ce];
                                    if (inCycle[ch] == 0) {
                                        long sum = (dp0[ch] + dp1[ch]) % kMod;
                                        ways0 = (ways0 * sum) % kMod;
                                        ways1 = (ways1 * dp0[ch]) % kMod;
                                    }
                                }
                                dp0[u] = ways0;
                                dp1[u] = ways1;
                                done[u] = 1;
                            }
                        }
                    }

                    a0 = (a0 * ((dp0[childVec] + dp1[childVec]) % kMod)) % kMod;
                    a1 = (a1 * dp0[childVec]) % kMod;
                }

                w0[i] = a0;
                w1[i] = a1;
            }

            long componentCount = 0;
            if (m == 1) {
                componentCount = w0[0];
            } else {
                long dpPrev0 = w0[0];
                long dpPrev1 = 0;
                for (int i = 1; i < m; ++i) {
                    long ndp0 = ((dpPrev0 + dpPrev1) % kMod * w0[i]) % kMod;
                    long ndp1 = (dpPrev0 * w1[i]) % kMod;
                    dpPrev0 = ndp0;
                    dpPrev1 = ndp1;
                }
                componentCount = (componentCount + dpPrev0 + dpPrev1) % kMod;

                dpPrev0 = 0;
                dpPrev1 = w1[0];
                for (int i = 1; i < m; ++i) {
                    long ndp0 = ((dpPrev0 + dpPrev1) % kMod * w0[i]) % kMod;
                    long ndp1 = (dpPrev0 * w1[i]) % kMod;
                    dpPrev0 = ndp0;
                    dpPrev1 = ndp1;
                }
                componentCount = (componentCount + dpPrev0) % kMod;
            }

            answer = (answer * componentCount) % kMod;
        }

        return Long.toString(answer);
    }

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