VirtualData has just found two binary set \(A_1, A_2, \cdots, A_n\) and \(B_1, B_2, \cdots, B_n\) (\(A_i, B_i ∈ \text{{0, 1}}\) for all \(1 \leq i \leq n\)) from his virtual machine! He would like to perform the operation described below exactly twice, so that \(A_i = B_i\) holds for all \(1 \leq i \leq n\) after the two operations.
The operation is: Select two integers \(l\) and \(r\) (\(1 \leq l \leq r \leq n\)), change \(A_i\) to \((1 - A_i)\) for all \(l \leq i \leq r\). VirtualData would like to know the number of ways to do so.
We use the following rules to determine whether two ways are different:
- Let Operation \(X = (a_1, a_2, a_3, a_4)\), where \(1 \leq a_1 \leq a_2 \leq n\), \(1 \leq a_3 \leq a_4 \leq n\), be a valid operation pair denoting that VirtualData selects integers \(a_1\) and \(a_2\) for the first operation and integers \(a_3\) and \(a_4\) for the second operation.
- Let Operation \(Y = (b_1, b_2, b_3, b_4)\), where \(1 \leq b_1 \leq b_2 \leq n\), \(1 \leq b_3 \leq b_4 \leq n\), be another valid operation pair denoting that VirtualData selects integers \(b_1\) and \(b_2\) for the first operation and integers \(b_3\) and \(b_4\) for the second operation.
- Operation \(X\) and Operation \(Y\) are considered different if there exists an integer \(k\) (\(1 \leq k \leq 4\)) such that .\(a_k \neq b_k\).
Input format
- The first line contains an integer n, denoting the length of binary sequence \(A\) and \(B\).
- The second line contains a binary string of size \(n\), denoting the set \(A\).
- The third line contains a binary string of size \(n\), denoting the set \(B\).
Output format
Print an integer in a new line, representing the number of unique ways given operation can be performed.
Constraints
\(1 \leq n \leq 10^6\)
In this case, we have the following options, (0 based indexing):
- Select [2, 3] , set A become 00110, then we select interval [5, 5] and set A becomes 00111 . So, this is one way to make the sequences identical.
- Select [5, 5] , set A become 01011, then we select interval [2, 3] and set A becomes 00111 . So, this is one way to make the sequences identical.
- Select [2, 5] , set A become 00101, then we select interval [4, 4] and set A becomes 00111 . So, this is one way to make the sequences identical.
- Select [4, 4] , set A become 01000, then we select interval [2, 5] and set A becomes 00111 . So, this is one way to make the sequences identical.
- Select [2, 4] , set A become 00100, then we select interval [4, 5] and set A becomes 00111 . So, this is one way to make the sequences identical.
- Select [4, 5] , set A become 01001, then we select interval [2, 4] and set A becomes 00111 . So, this is one way to make the sequences identical.
So, there are a total of 6 distinct ways to perform the operations and make both sequences identical, hence the output is 6.
