7. Dobrý recept

Jedno z najvýnosnejších čokoládových obchodných partnerstiev je medzi FKS (Francúzski Kuchári Sladkostí) a KMS (Konfederácia Maškrtných Spoločností) – tri čokolády od FKSákov sú medzi KMSákmi veľmi obľúbené. Táto zlatá baňa však neunikla pozornosti KSP (Komora Slovenských Pekárov), a tak sa na poslednom zasadnutí rozhodli, že do budúceho roku vyvinú novú čokoládu, ktorou by mohli FKS konkurovať.

Bolo im však jasné, že na to, aby ich čokoláda zožala úspech, nesmie chutiť príliš podobne ako niektorá čokoláda, ktorú pre KMS dodávajú FKS (vďaka obchodnému partnerstvu majú totiž výhodné ceny). Rozhodli sa teda, že ich nová čokoláda musí mať rovnaký chuťový rozdiel od všetkých troch FKS čokolád.

Každá čokoláda na svete sa dá popísať ingredienciami, ktoré sa použivajú na jej prípravu. Chuť čokolády závisí len na jej ingredienciách – teda rozdiel chutí dvoch čokolád je jednoducho počet ingrediencií, v ktorých sa čokolády líšia.

KSP teraz zaujíma koľko rôznych receptov na čokoládu by malo šancu na úspech.

Úloha

Na svete existuje \(n\) ingrediencií, ktoré sa môžu použiť na prípravu čokolády. Recept na čokoládu je teda reťazec dĺžky \(n\), kde \(i\)-ty znak je 1 alebo 0, podľa toho, či čokoláda \(i\)-tu ingredienciu obsahuje, alebo nie. Pre účely tejto úlohy budeme za recepty na čokoládu považovať všetky takéto reťazce (vrátane reťazca tvoreného samými nulami). Rozdiel chutí dvoch čokolád je počet takých ingrediencií, že jedna z čokolád ju obsahuje, ale druhá nie.

Zistite, koľko rôznych receptov na čokoládu má rovnaký rozdiel chutí od všetkých troch FKS čokolád.

Formát vstupu

V prvom riadku je celé číslo \(n\) (\(1 \leq n \leq 3\cdot 10^5\)) – počet ingrediencií použiteľných na prípravu čokolády.

Nasledujú tri binárne reťazce dĺžky \(n\), každý na samostatnom riadku – recepty FKS čokolád.

Je osem sád testovacích vstupov. Maximálne hodnoty \(n\) v jednotlivých sadách sú nasledovné:

Navyše, na získanie plného počtu za popis stačí riešenie s časovou zložitosťou \(O(n \log n)\). Za dobrý popis s lepšou zložitosťou je možné získať (najviac dva) bonusové body.

Formát výstupu

Nájdite počet čokolád, ktorých rozdiel chutí je rovnaký od všetkých troch FKS čokolád. Keďže tento počet môže byť veľmi veľký, vypíšte jeho zvyšok po delení veľkým prvočíslom \(p\).

Vo všetkých vstupoch bude platiť, že \(p = 1\,000\,000\,007\), avšak pri odhade časovej zložitosti toto číslo nepovažujte za konštantu. Môžete predpokladať, že \(n\) je rádovo menej ako \(p\), avšak nie príliš menej. Riešenie so zložitošťou \(O(n)\) je teda oveľa lepšie ako riešenie so zložitosťou \(O(p)\). Dokonca aj \(O(n^{10})\) je stále lepšie ako \(O(p)\). Na druhú stranu môžete predpokladať, že \(O(\log p) = O(\log n)\), resp. že rozdiel medzi \(n\) a \(p\) je nanajvýš polynomiálny.¹ Pri popise riešenia môžete predpokladať, že \(p\) je prvočíslo.

Príklady

Input:

3
101
110
000

Output:

2

Jednou možnosťou je použiť len prvú ingredienciu. Druhou je použiť práve druhú a tretiu.

Input:

6
111111
000000
101110

Output:

12