题目地址：http://codeforces.com/contest/1017/problem/B

B. The Bits

Rudolf is on his way to the castle. Before getting into the castle, the security staff asked him a question:

Given two binary numbers aa and bb of length nn. How many different ways of swapping two digits in aa (only in aa, not bb) so that bitwise OR of these two numbers will be changed? In other words, let cc be the bitwise OR of aa and bb, you need to find the number of ways of swapping two bits in aa so that bitwise OR will not be equal to cc.

Note that binary numbers can contain leading zeros so that length of each number is exactly nn.

Bitwise OR is a binary operation. A result is a binary number which contains a one in each digit if there is a one in at least one of the two numbers. For example, 010102010102 OR 100112100112 = 110112110112.

Well, to your surprise, you are not Rudolf, and you don't need to help him…… You are the security staff! Please find the number of ways of swapping two bits in aa so that bitwise OR will be changed.

Input

The first line contains one integer nn (2≤n≤1052≤n≤105) — the number of bits in each number.

The second line contains a binary number aa of length nn.

The third line contains a binary number bb of length nn.

Output

Print the number of ways to swap two bits in aa so that bitwise OR will be changed.

Examples

input

Copy

5
01011
11001

output

Copy

input

Copy

6
011000
010011

output

Copy

首先说一下按位或运算，对于a|b：

0 | 0 = 0；

0 | 1 = 1；

1 | 0 = 1；

1 | 1 = 1； //一真俱真

题意：给你两个长度为n的01串，可以交换a串中任意两个01的位置，使其中一处的a|b的值发生改变，求出所有交换方法的种数。

例如：
01011
11001
第一列的01的位或值为1，第四列的10位或值为1.交换a串中01的位置后变成：
11001
11001
第一列的值变为1，第四列的值变为0.则交换成功。

于是对于样例一：

5
01011
11001
可以交换的位置有：

(1,4) 第四列的值由1变0；

(2,3)  第三列的值由1变0；

(3,4)  第三列的值由0变1，第四列的值由1变0；；

(3,5)  第三列的值由1变0；

共四种。

那么总结一下，对于两个二进制数a、b，每个对应的01位有四种情况：

1.a[i]=0,b[i]=0; 则应与另一个a[j]=1,b[j]=1/0 交换；

2.a[i]=0,b[i]=1; 则应与另一个a[j]=1,b[j]=0 交换；

3.a[i]=1,b[i]=0; 则应与另一个a[j]=0,b[j]=1/0 交换；

4.a[i]=1,b[i]=1; 则应与另一个a[j]=0,b[j]=0 交换；

由上表可以看出，第1种情况可与3,4进行交换，第2种情况可与3交换，从而我们只需找出符合1,2两种情况的01子串的总数，分别乘以3,4情况的总数，即可求出所有的交换方法总数。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long

int main()
{
	ll n,i,j,sum,s[5]={0};    //结果可能会爆int
	string a,b;
	cin>>n;
	cin>>a>>b;
	for(i=0;i<n;i++)
	{
		if(a[i]=='0')
		{
			if(b[i]=='0')
				s[1]++;
			else
				s[2]++;
		}
		else
		{
			if(b[i]=='0')
				s[3]++;
			else
				s[4]++;
		}
	}
	sum=s[1]*(s[3]+s[4])+s[2]*s[3];
	cout<<sum<<endl;
	return 0;
}

【CF 1017B】 The Bits 按位或运算

B. The Bits