DreamGrid's Binary Flip Operations

DreamGrid has discovered two binary sequences \(s_1, s_2, \dots, s_n\) and \(t_1, t_2, \dots, t_n\) (with \(s_i, t_i \in \{0,1\}\) for \(1 \le i \le n\)) from his virtual machine. He wishes to transform sequence \(s\) into \(t\) by performing exactly two operations.

The operation is defined as follows: select two integers \(l\) and \(r\) (\(1 \le l \le r \le n\)) and flip every bit of \(s_i\) for \(l \le i \le r\), i.e. change \(s_i\) to \(1 - s_i\). After performing the two operations sequentially, the resulting sequence must satisfy \(s_i = t_i\) for all \(1 \le i \le n\).

Two ways are considered different if their 4-tuple \((a_1, a_2, a_3, a_4)\) is different, where the first operation uses \(a_1\) and \(a_2\) as its left and right indices, and the second uses \(a_3\) and \(a_4\) respectively.

Note: All indices are 1-indexed. (For this problem, you may assume \(1 \le n \le 20\).)

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 20\)).

The second line contains a binary string of length \(n\), representing sequence \(s\).

The third line contains a binary string of length \(n\), representing sequence \(t\).

Both strings consist only of the characters '0' and '1'.

outputFormat

Output a single integer: the number of ways to perform exactly two operations (each defined by a contiguous interval to flip) such that after the two operations, the sequence \(s\) becomes equal to \(t\).

sample

3
101
010

2