该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小明有一个2×n的方格棋盘，他已经把这个2×n的方格棋盘用1×2或者2×1的多米诺骨牌不重叠的覆盖满了，现在他想给这些棋盘上的每一个骨牌涂上红、黄、蓝三种颜色。

但是他不想让任何相邻的骨牌涂上相同颜色，他想请你求出这么做的方案数有多少？

因为答案可能很大，你需要输出答案对1000000007取余数的结果。

Format

Input

第一行一个正整数n（1<=n<=52）

第二行和第三行两个字符串，描述一个放满骨牌的棋盘，字符串长度为n，用两个相邻的相同字符表示一个骨牌。

每个字符均为大写或者小写英文字母。

Output

输出一个正整数，即答案

Sample 1

Input

3
aaB
ccB

Output

6

Limitation

1s, 64MB for each test case.

Source

2019网宿杯XMU程序设计竞赛网络预赛第一场