import java.util.*; import java.io.*; class Main { private static final void solve() throws IOException { int n = (1 << ni()) - 1; var g = new ArrayList>(n); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int i = 2; i <= n; i++) { int u = i - 1, v = i / 2 - 1; g.get(u).add(v); g.get(v).add(u); } var uu = sc.nextCharArray(); var vv = sc.nextCharArray(); int u = 0, v = 0; for (char c : uu) u = (u << 1) | (c - '0'); for (char c : vv) v = (v << 1) | (c - '0'); u--; v--; g.get(u).add(v); g.get(v).add(u); long ans = 0L; final int mod = 998244353; var d = new int[n]; final int inf = (int) 1e7; var q = new ArrayDeque(); for (int st = 0; st < n; st++) { Arrays.fill(d, inf); d[st] = 0; q.add(st); while (!q.isEmpty()) { int x = q.remove(); for (int i : g.get(x)) { if (d[i] != inf) continue; d[i] = d[x] + 1; q.add(i); } } for (int i : d) ans += i; ans %= mod; } if (ans % 2 != 0) ans += mod; ans /= 2; if (ans < 0) ans += mod; ou.println(ans); } public static void main(String[] args) throws IOException { solve(); ou.flush(); } private static final int ni() throws IOException { return sc.nextInt(); } private static final int[] ni(int n) throws IOException { return sc.nextIntArray(n); } private static final long nl() throws IOException { return sc.nextLong(); } private static final long[] nl(int n) throws IOException { return sc.nextLongArray(n); } private static final String ns() throws IOException { return sc.next(); } private static final ContestInputStream sc = new ContestInputStream(); private static final ContestOutputStream ou = new ContestOutputStream(); } class Convolution { private static int primitiveRoot(int m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 998244353) return 3; int[] divs = new int[20]; divs[0] = 2; int cnt = 1; int x = (m - 1) >> 1; while ((x & 1) == 0) x >>= 1; for (int i = 3; i * (long) i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } } if (x > 1) divs[cnt++] = x; for (int g = 2;; g++) { boolean ok = true; for (int i = 0; i < cnt; i++) { if (pow(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } private static long pow(long x, long n, int m) { if (m == 1) return 0; long r = 1; long y = x % m; while (n > 0) { if ((n & 1) != 0) r = (r * y) % m; y = (y * y) % m; n >>= 1; } return r; } private static int ceilPow2(int n) { int x = 0; while ((1L << x) < n) x++; return x; } private static long garner(long[] c, int[] mods) { int n = c.length + 1; long[] cnst = new long[n]; long[] coef = new long[n]; Arrays.fill(coef, 1); for (int i = 0; i < n - 1; i++) { int m1 = mods[i]; long v = (c[i] - cnst[i] + m1) % m1; v = v * pow(coef[i], m1 - 2, m1) % m1; for (int j = i + 1; j < n; j++) { long m2 = mods[j]; cnst[j] = (cnst[j] + coef[j] * v) % m2; coef[j] = coef[j] * m1 % m2; } } return cnst[n - 1]; } private static long[] sumE(int mod, int g) { long[] sum_e = new long[30]; long[] es = new long[30]; long[] ies = new long[30]; int cnt2 = Integer.numberOfTrailingZeros(mod - 1); long e = pow(g, (mod - 1) >> cnt2, mod); long ie = pow(e, mod - 2, mod); for (int i = cnt2; i >= 2; i--) { es[i - 2] = e; ies[i - 2] = ie; e = e * e % mod; ie = ie * ie % mod; } long now = 1; for (int i = 0; i < cnt2 - 2; i++) { sum_e[i] = es[i] * now % mod; now = now * ies[i] % mod; } return sum_e; } private static long[] sumIE(int mod, int g) { long[] sum_ie = new long[30]; long[] es = new long[30]; long[] ies = new long[30]; int cnt2 = Integer.numberOfTrailingZeros(mod - 1); long e = pow(g, (mod - 1) >> cnt2, mod); long ie = pow(e, mod - 2, mod); for (int i = cnt2; i >= 2; i--) { es[i - 2] = e; ies[i - 2] = ie; e = e * e % mod; ie = ie * ie % mod; } long now = 1L; for (int i = 0; i < cnt2 - 2; i++) { sum_ie[i] = ies[i] * now % mod; now = now * es[i] % mod; } return sum_ie; } private static void butterflyInv(long[] a, long[] sumIE, int mod) { int n = a.length; int h = ceilPow2(n); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); long inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p]; a[i + offset] = (l + r) % mod; a[i + offset + p] = (mod + l - r) * inow % mod; } int x = Integer.numberOfTrailingZeros(~s); inow = inow * sumIE[x] % mod; } } } private static void butterfly(long[] a, long[] sumE, int mod) { int n = a.length; int h = ceilPow2(n); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); long now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { long l = a[i + offset]; long r = a[i + offset + p] * now % mod; a[i + offset] = (l + r) % mod; a[i + offset + p] = (l - r + mod) % mod; } int x = Integer.numberOfTrailingZeros(~s); now = now * sumE[x] % mod; } } } public static long[] convolution(long[] a, long[] b, int mod) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; int z = 1 << ceilPow2(n + m - 1); { long[] na = new long[z]; long[] nb = new long[z]; System.arraycopy(a, 0, na, 0, n); System.arraycopy(b, 0, nb, 0, m); a = na; b = nb; } int g = primitiveRoot(mod); long[] sume = sumE(mod, g); long[] sumie = sumIE(mod, g); butterfly(a, sume, mod); butterfly(b, sume, mod); for (int i = 0; i < z; i++) a[i] = a[i] * b[i] % mod; butterflyInv(a, sumie, mod); a = Arrays.copyOf(a, n + m - 1); long iz = pow(z, mod - 2, mod); for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod; return a; } public static long[] convolutionLL(long[] a, long[] b, int mod) { int n = a.length; int m = b.length; if (n == 0 || m == 0) return new long[0]; int mod1 = 754974721; int mod2 = 167772161; int mod3 = 469762049; long[] c1 = convolution(a, b, mod1); long[] c2 = convolution(a, b, mod2); long[] c3 = convolution(a, b, mod3); int retSize = c1.length; long[] ret = new long[retSize]; int[] mods = { mod1, mod2, mod3, mod }; for (int i = 0; i < retSize; ++i) ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods); return ret; } public static long[] inv(long[] f) { final int mod = 998244353; int n = f.length; int c = 1; var g = new long[c]; g[0] = pow(f[0], mod - 2, mod); while (c < n) { c <<= 1; var t = Arrays.copyOf(Convolution.convolution(g, Arrays.copyOf(f, c), mod), c); t[0] = mod + 2 - t[0]; for (int i = 1; i < c; i++) t[i] = mod - t[i]; g = Arrays.copyOf(Convolution.convolution(g, t, mod), c); } return Arrays.copyOf(g, n); } public static long[] convolutionNaive(long[] a, long[] b, int mod) { int n = a.length; int m = b.length; int k = n + m - 1; long[] ret = new long[k]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ret[i + j] += a[i] * b[j] % mod; ret[i + j] %= mod; } } return ret; } } final class ContestInputStream extends FilterInputStream { protected final byte[] buf; protected int pos = 0; protected int lim = 0; private final char[] cbuf; public ContestInputStream() { super(System.in); this.buf = new byte[1 << 13]; this.cbuf = new char[1 << 20]; } boolean hasRemaining() throws IOException { if (pos < lim) return true; lim = in.read(buf); pos = 0; return lim > 0; } final int remaining() throws IOException { if (pos >= lim) { lim = in.read(buf); pos = 0; } return lim - pos; } @Override public final int available() throws IOException { if (pos < lim) return lim - pos + in.available(); return in.available(); } @Override public final long skip(long n) throws IOException { if (pos < lim) { int rem = lim - pos; if (n < rem) { pos += n; return n; } pos = lim; return rem; } return in.skip(n); } @Override public final int read() throws IOException { if (hasRemaining()) return buf[pos++]; return -1; } @Override public final int read(byte[] b, int off, int len) throws IOException { if (pos < lim) { int rem = Math.min(lim - pos, len); for (int i = 0; i < rem; i++) b[off + i] = buf[pos + i]; pos += rem; return rem; } return in.read(b, off, len); } public final char[] readToken() throws IOException { int cpos = 0; int rem; byte b; l: while ((rem = remaining()) > 0) { for (int i = 0; i < rem; i++) { b = buf[pos + i]; if (b <= 0x20) { pos += i + 1; cpos += i; if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a) pos++; break l; } cbuf[cpos + i] = (char) b; } pos += rem; cpos += rem; } char[] arr = new char[cpos]; for (int i = 0; i < cpos; i++) arr[i] = cbuf[i]; return arr; } public final int readToken(char[] cbuf, int off) throws IOException { int cpos = off; int rem; byte b; l: while ((rem = remaining()) > 0) { for (int i = 0; i < rem; i++) { b = buf[pos + i]; if (b <= 0x20) { pos += i + 1; cpos += i; if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a) pos++; break l; } cbuf[cpos + i] = (char) b; } pos += rem; cpos += rem; } return cpos - off; } public final int readToken(char[] cbuf) throws IOException { return readToken(cbuf, 0); } public final String next() throws IOException { int cpos = 0; int rem; byte b; l: while ((rem = remaining()) > 0) { for (int i = 0; i < rem; i++) { b = buf[pos + i]; if (b <= 0x20) { pos += i + 1; cpos += i; if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a) pos++; break l; } cbuf[cpos + i] = (char) b; } pos += rem; cpos += rem; } return String.valueOf(cbuf, 0, cpos); } public final char[] nextCharArray() throws IOException { return readToken(); } public final int nextInt() throws IOException { if (!hasRemaining()) return 0; int value = 0; byte b = buf[pos++]; if (b == 0x2d) { while (hasRemaining() && (b = buf[pos++]) > 0x20) value = value * 10 - b + 0x30; } else { do { value = value * 10 + b - 0x30; } while (hasRemaining() && (b = buf[pos++]) > 0x20); } if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a) pos++; return value; } public final long nextLong() throws IOException { if (!hasRemaining()) return 0L; long value = 0L; byte b = buf[pos++]; if (b == 0x2d) { while (hasRemaining() && (b = buf[pos++]) > 0x20) value = value * 10 - b + 0x30; } else { do { value = value * 10 + b - 0x30; } while (hasRemaining() && (b = buf[pos++]) > 0x20); } if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a) pos++; return value; } public final char nextChar() throws IOException { if (!hasRemaining()) throw new EOFException(); final char c = (char) buf[pos++]; if (hasRemaining() && buf[pos++] == 0x0d && hasRemaining() && buf[pos] == 0x0a) pos++; return c; } public final float nextFloat() throws IOException { return Float.parseFloat(next()); } public final double nextDouble() throws IOException { return Double.parseDouble(next()); } public final boolean[] nextBooleanArray(char ok) throws IOException { char[] s = readToken(); int n = s.length; boolean[] t = new boolean[n]; for (int i = 0; i < n; i++) t[i] = s[i] == ok; return t; } public final boolean[][] nextBooleanMatrix(int h, int w, char ok) throws IOException { boolean[][] s = new boolean[h][]; for (int i = 0; i < h; i++) { char[] t = readToken(); int n = t.length; s[i] = new boolean[n]; for (int j = 0; j < n; j++) s[i][j] = t[j] == ok; } return s; } public final String[] nextStringArray(int len) throws IOException { String[] arr = new String[len]; for (int i = 0; i < len; i++) arr[i] = next(); return arr; } public final int[] nextIntArray(int len) throws IOException { int[] arr = new int[len]; for (int i = 0; i < len; i++) arr[i] = nextInt(); return arr; } public final int[] nextIntArray(int len, java.util.function.IntUnaryOperator map) throws IOException { int[] arr = new int[len]; for (int i = 0; i < len; i++) arr[i] = map.applyAsInt(nextInt()); return arr; } public final long[] nextLongArray(int len, java.util.function.LongUnaryOperator map) throws IOException { long[] arr = new long[len]; for (int i = 0; i < len; i++) arr[i] = map.applyAsLong(nextLong()); return arr; } public final int[][] nextIntMatrix(int h, int w) throws IOException { int[][] arr = new int[h][w]; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) arr[i][j] = nextInt(); return arr; } public final int[][] nextIntMatrix(int h, int w, java.util.function.IntUnaryOperator map) throws IOException { int[][] arr = new int[h][w]; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) arr[i][j] = map.applyAsInt(nextInt()); return arr; } public final long[] nextLongArray(int len) throws IOException { long[] arr = new long[len]; for (int i = 0; i < len; i++) arr[i] = nextLong(); return arr; } public final long[][] nextLongMatrix(int h, int w) throws IOException { long[][] arr = new long[h][w]; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) arr[i][j] = nextLong(); return arr; } public final float[] nextFloatArray(int len) throws IOException { float[] arr = new float[len]; for (int i = 0; i < len; i++) arr[i] = nextFloat(); return arr; } public final double[] nextDoubleArray(int len) throws IOException { double[] arr = new double[len]; for (int i = 0; i < len; i++) arr[i] = nextDouble(); return arr; } public final char[][] nextCharMatrix(int h, int w) throws IOException { char[][] arr = new char[h][]; for (int i = 0; i < h; i++) arr[i] = readToken(); return arr; } public final void nextThrow() throws IOException { next(); return; } public final void nextThrow(int n) throws IOException { for (int i = 0; i < n; i++) nextThrow(); return; } } final class ContestOutputStream extends FilterOutputStream implements Appendable { protected final byte[] buf; protected int pos = 0; public ContestOutputStream() { super(System.out); this.buf = new byte[1 << 13]; } @Override public void flush() throws IOException { out.write(buf, 0, pos); pos = 0; out.flush(); } void put(byte b) throws IOException { if (pos >= buf.length) flush(); buf[pos++] = b; } int remaining() throws IOException { if (pos >= buf.length) flush(); return buf.length - pos; } @Override public void write(int b) throws IOException { put((byte) b); } @Override public void write(byte[] b, int off, int len) throws IOException { int o = off; int l = len; while (l > 0) { int rem = Math.min(remaining(), l); for (int i = 0; i < rem; i++) buf[pos + i] = b[o + i]; pos += rem; o += rem; l -= rem; } } @Override public ContestOutputStream append(char c) throws IOException { put((byte) c); return this; } @Override public ContestOutputStream append(CharSequence csq, int start, int end) throws IOException { int off = start; int len = end - start; while (len > 0) { int rem = Math.min(remaining(), len); for (int i = 0; i < rem; i++) buf[pos + i] = (byte) csq.charAt(off + i); pos += rem; off += rem; len -= rem; } return this; } @Override public ContestOutputStream append(CharSequence csq) throws IOException { return append(csq, 0, csq.length()); } public ContestOutputStream append(char[] arr, int off, int len) throws IOException { int o = off; int l = len; while (l > 0) { int rem = Math.min(remaining(), l); for (int i = 0; i < rem; i++) buf[pos + i] = (byte) arr[o + i]; pos += rem; o += rem; l -= rem; } return this; } public ContestOutputStream print(char[] arr) throws IOException { return append(arr, 0, arr.length).newLine(); } public ContestOutputStream print(boolean value) throws IOException { if (value) return append("o"); return append("x"); } public ContestOutputStream println(boolean value) throws IOException { if (value) return append("o\n"); return append("x\n"); } public ContestOutputStream print(boolean[][] value) throws IOException { final int n = value.length, m = value[0].length; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) print(value[i][j]); newLine(); } return this; } public ContestOutputStream print(int value) throws IOException { return append(String.valueOf(value)); } public ContestOutputStream println(int value) throws IOException { return append(String.valueOf(value)).newLine(); } public ContestOutputStream print(long value) throws IOException { return append(String.valueOf(value)); } public ContestOutputStream println(long value) throws IOException { return append(String.valueOf(value)).newLine(); } public ContestOutputStream print(float value) throws IOException { return append(String.valueOf(value)); } public ContestOutputStream println(float value) throws IOException { return append(String.valueOf(value)).newLine(); } public ContestOutputStream print(double value) throws IOException { return append(String.valueOf(value)); } public ContestOutputStream println(double value) throws IOException { return append(String.valueOf(value)).newLine(); } public ContestOutputStream print(char value) throws IOException { return append(value); } public ContestOutputStream println(char value) throws IOException { return append(value).newLine(); } public ContestOutputStream print(String value) throws IOException { return append(value); } public ContestOutputStream println(String value) throws IOException { return append(String.valueOf(value)).newLine(); } public ContestOutputStream print(Object value) throws IOException { return append(String.valueOf(value)); } public ContestOutputStream println(Object value) throws IOException { return append(String.valueOf(value)).newLine(); } public ContestOutputStream printYN(boolean yes) throws IOException { if (yes) return println("Yes"); return println("No"); } public ContestOutputStream printAB(boolean yes) throws IOException { if (yes) return println("Alice"); return println("Bob"); } public ContestOutputStream print(CharSequence[] arr) throws IOException { if (arr.length > 0) { append(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').append(arr[i]); } return this; } public ContestOutputStream print(int[] arr) throws IOException { if (arr.length > 0) { print(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').print(arr[i]); } newLine(); return this; } public ContestOutputStream print(int[] arr, int length) throws IOException { if (length > 0) print(arr[0]); for (int i = 1; i < length; i++) append('\u0020').print(arr[i]); newLine(); return this; } public ContestOutputStream println(int[] arr) throws IOException { for (int i : arr) print(i).newLine(); return this; } public ContestOutputStream println(int[] arr, int length) throws IOException { for (int i = 0; i < length; i++) println(arr[i]); return this; } public ContestOutputStream print(boolean[] arr) throws IOException { if (arr.length > 0) { print(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').print(arr[i]); } newLine(); return this; } public ContestOutputStream print(long[] arr) throws IOException { if (arr.length > 0) { print(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').print(arr[i]); } newLine(); return this; } public ContestOutputStream print(long[] arr, int length) throws IOException { if (length > 0) print(arr[0]); for (int i = 1; i < length; i++) append('\u0020').print(arr[i]); newLine(); return this; } public ContestOutputStream println(long[] arr, int length) throws IOException { for (int i = 0; i < length; i++) println(arr[i]); return this; } public ContestOutputStream println(long[] arr) throws IOException { for (long i : arr) print(i).newLine(); return this; } public ContestOutputStream print(float[] arr) throws IOException { if (arr.length > 0) { print(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').print(arr[i]); } return this; } public ContestOutputStream println(float[] arr) throws IOException { for (float i : arr) print(i).newLine(); return this; } public ContestOutputStream print(double[] arr) throws IOException { if (arr.length > 0) { print(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').print(arr[i]); } return newLine(); } public ContestOutputStream println(double[] arr) throws IOException { for (double i : arr) print(i).newLine(); return this; } public ContestOutputStream print(Object[] arr) throws IOException { if (arr.length > 0) { print(arr[0]); for (int i = 1; i < arr.length; i++) append('\u0020').print(arr[i]); } return newLine(); } public ContestOutputStream print(java.util.ArrayList arr) throws IOException { if (!arr.isEmpty()) { final int n = arr.size(); print(arr.get(0)); for (int i = 1; i < n; i++) print(" ").print(arr.get(i)); } return newLine(); } public ContestOutputStream println(java.util.ArrayList arr) throws IOException { final int n = arr.size(); for (int i = 0; i < n; i++) println(arr.get(i)); return this; } public ContestOutputStream println(Object[] arr) throws IOException { for (Object i : arr) print(i).newLine(); return this; } public ContestOutputStream newLine() throws IOException { return append(System.lineSeparator()); } public ContestOutputStream endl() throws IOException { newLine().flush(); return this; } public ContestOutputStream print(int[][] arr) throws IOException { for (int[] i : arr) print(i); return this; } public ContestOutputStream print(long[][] arr) throws IOException { for (long[] i : arr) print(i); return this; } public ContestOutputStream print(char[][] arr) throws IOException { for (char[] i : arr) print(i); return this; } public ContestOutputStream print(Object[][] arr) throws IOException { for (Object[] i : arr) print(i); return this; } public ContestOutputStream println() throws IOException { return newLine(); } }