Задана дошка роміром \(2xN\) покрита \(N\) доміношками,які не накладаються одна на одну. Доміношка може покривати або прямокутник розміром \(1x2\), або розміром \(2x1\)
Необхідно розфарбувати доміношки в 3 кольори: червоний, блакитний, зелений. Дві доміношки які торкаються одна одну мають бути пофарбовані в різні кольори.
Визначіть скільки є способі розфарбувати доміно за вищевказаними правилами, і виведіть відповідь за модулем 1000000007.

Формат вхідних даних

В першому рядку число \(N\) (\(1 \le N \le 52\))
Далі два рядка з \(N\) маленьких або великих англійських літер. Кожна доміношка позначена однаковими літерами

Формат вихідних даних

Виведіть відповідь на задачу

Приклад вхідних даних-1

3
aab
ccb

Приклад вихідних даних-1

6

Пояснення до прикладу-1

Приклад вхідних даних-2

1
Z
Z

Приклад вихідних даних-2

3

Приклад вхідних даних-3

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

Приклад вихідних даних-3

958681902