← 返回题目列表

Codeforces · 296/B

B. 雅罗斯拉夫和两根弦

中文机器翻译题面 查看原题

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。