B. Яраслов ба 2 тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ярасловд $n$ урттай $s$ ба $w$ тэмдэгт мөрүүд байв. Хэрвээ $i$, $j$ ($1 ≤ i$, $j ≤ n$) хос тоо нь $s_i > w_i$ ба $s_j < w_j$ нөхцөлүүдийг хангаж байвал харьцуулж болшгүй тэмдэгт мөр гэж нэрлэе.

Тэмдэгт мөр нь цифрүүд болон асуултын тэмдгээс тогтоно.

Яраслов асуултын тэмдгүүдийг солих замаар хичнээн харьцуулж болшгүй тэмдэгт мөр үүсгэж чадах вэ? Тэмдэгт мөр нь $0$-ээр эхэлж болох ба асуултын тэмдгүүдийн оронд ижил цифр орлуулж болно, өөр өөр цифр орлуулж ч болно.

Бодлогын хариуг$1000000007$ ($10^9 + 7$)-д хуваасны үлдэгдлийг ол.

Оролт

Эхний мөрөнд $2$ тэмдэгт мөрийн уртыг илэрхийлэх $n$ ($1 ≤ n ≤ 10^5$), дараагийн хоёр мөрөнд цифр болон асуултын тэмдгээс тогтсон $n$ урттай тэмдэгт мөрүүд өгөгдөнө.

Гаралт

Бодлогын хариуг $1000000007$ ($10^9 + 7$)-д хуваасны үлдэгдлийг хэвлэнэ.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
2
90
09
Гаралт
1
Оролт
2
11
55
Гаралт
0
Оролт
5
?????
?????
Гаралт
993531194

Тэмдэглэл

The first test contains no question marks and both strings are incomparable, so the answer is $1$.

The second test has no question marks, but the given strings are comparable, so the answer is $0$.

Сэтгэгдлүүдийг ачааллаж байна...