Yaroslav 认为,如果有两个数字 i 和 j (1 ≤ i, j ≤ n),且 si > wi 且 sj < wj,则两个由数字组成且长度为 n 的字符串 s 和 w 是不可比较的。这里符号si代表字符串s的第i位,类似地,wj代表字符串w的第j位。
字符串的模板是由数字和问号(“?”)组成的字符串。
Yaroslav 有两个字符串模板,每个模板的长度为 n。 Yaroslav 想要统计两个模板中将所有问号替换为某些整数的方法的数量,从而使生成的字符串具有不可比性。请注意,获得的字符串可以包含前导零,并且不同的问号可以替换为不同或相同的整数。
帮助 Yaroslav,计算所描述的路数除以 1000000007 (109 + 7) 后的余数。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 两个模板的长度。第二行包含第一个模板——一个由数字和字符“?”组成的字符串。字符串的长度等于n。第三行包含相同格式的第二个模板。
输出
在一行中打印问题答案除以数字 1000000007 (109 + 7) 后的余数。
示例
输入 #1
2 90 09
输出 #1
1
输入 #2
2 11 55
输出 #2
0
输入 #3
5 ????? ?????
输出 #3
993531194
注意
第一个测试不包含问号,并且两个字符串不可比较,因此答案为 1。
第二个测试没有问号,但给定的字符串是可比较的,所以答案是0。