SpiridușiAdvanced

ASG s-a jucat prea mult Fortnite. A vrut să se bage în pat, însă Flaviu îl aștepta acolo. Acesta nu a știut să rezolve o problemă la matematică cu restul împărțirii de la școală și i-a cerut ajutorul. Între timp, a venit Spiridușul Binar care i-a dat tema lui Flaviu și, știindu-l mai informatician din fire, i-a dat o problemă mult mai grea, deoarece are încredere în ASG să-i salveze poporul.

Spiridușul Binar face parte din regatul digital Bitlandia, unde există două orașe: Bitești și Octești. Aceste orașe sunt în competiție constantă să vadă cine poate genera cel mai puternic semnal. Fiecare oraș are un dispozitiv de criptare care ia două chei $a$ și $b$, și le combină cu o frecvență de modulare $x$ pentru a calcula puterea semnalului, prin operația $(a \oplus x) \cdot (b \oplus x)$, unde $\oplus$ reprezintă operația xor.

Cerință

Ajutați-l pe Spiriduș să găsească puterea semnalului maximă ce se poate forma cu cheile $a$ și $b$, pentru a-i întrece pe cei din orașul Octești.

Puterea semnalului poate fi foarte mare, așadar să se afișeze puterea modulo $1\ 000\ 741\ 823$.

Date de intrare

Pe prima linie se găsește numărul $N$, ce reprezintă lungimea maximă a cheilor.

Pe a doua linie se găsește șirul binar $A$, iar pe a treia linie șirul binar $B$, ambele de lungime $N$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, anume puterea semnalului maximă modulo $1\ 000\ 741\ 823$.

Restricții și precizări

• $1 \leq N \leq 1\ 000$;
• $1 \leq A, B \leq 2^N$.
• $0 \leq x \leq 2^N$.
• $A$ și $B$ au aceeași lungime.

Exemplul 1

stdin

5
10101
00110

stdout

420

Explicație

Șirul binar $A$ este numărul $21$, iar celălalt este numărul $6$. Pentru $x = 2$, avem $(21 \oplus 2) \cdot (6 \oplus 2) = 92$. Pentru $x = 8$, avem $(21 \oplus 8) \cdot (6 \oplus 8) = 238$. $x = 9$ oferă puterea maximă de $420$.

Exemplul 2

stdin

7
1110101
0010110

stdout

5796

Explicație

Șirul $A$ reprezintă numărul $117$ și șirul $B$ reprezintă numărul $22$. Puterea maximă este atinsă în $x = 41$ și $x = 74$.