D. Бөмбөг дэлбэлэгч 1D

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

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

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

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

"Бөмбөг дэлбэлэгч 1D" тоглоомыг квадратуудын мөр дээр тоглодог ба өндөр нь 1 квадрат, өргөн нь $n$ квадратууд байна. Зарим квадрат нь бөмбөг агуулдаг ба хэрвээ квадрат бөмбөг агуулаагүй бол 0-2 хүртэлх цифрийг агуулна. Энэ цифр нь зэргэлдээх квадратуудынх нь бөмбөгний тоо юм.

Жишээлбэл, тоглох зөв талбар нь ингэж харагддаг: $001*2***101*$. "$*$"-р тэмдэглэгдсэн нүднүүд нь бөмбөг агуулсан байна. Зөв талбар дээрх тоонууд нь зэргэлдээх нүднүүдийн бөмбөгнүүдийн тоог илэрхийлнэ. Жишээлбэл, $2*$ зөв биш учир нь 2 утгатай нүдний зэргэлдээх хоёр нүднүүдэд бөмбөг байх ёстой.

Валера "бөмбөг дэлбэлэгч 1D" тоглох зөв талбар хийхийг хүсч байна. Тэр $n$ нүдний өргөнтэй талбарын квадратуудыг аль хэдийн зураад, зарим нүднүүдэд тоо тавьсан ба зарим нүднүүдэд бөмбөг тавьсан байна. Хэрвээ талбарыг зөв дуусгах ёстой бол үлдсэн нүднүүдийг бөмбөг болон тоогоор бөглөх хэдэн арга байгааг тэр бодож байна.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $s_{1}s_{2}... s_{n}$ $(1 ≤ n ≤ 10^{6})$ тэмдэгтүүдийн дарааллыг оруулна, "$0$", "$1$", "$2$" цифрүүд болон "$*$", "$?$" тэмдэгтүүдийг агуулна. Хэрвээ $s_{i}$ нүд "$*$" бол талбарын $i$-р нүд бөмбөг агуулна. Хэрвээ $s_{i}$ нүд "$?$" бол Валера $i$-р нүдэнд ямар тэмдэг тавихаа хараахан шийдээгүй байгаа гэсэн үг юм. $s_{i}$ нь цифр бол энэ нь $i$-р талбарт бичигдсэн цифрийг илэрхийлнэ.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ тоо нь талбарыг зөв байлгахын тулд хоосон нүднүүдийг бөглөх аргуудын тоо юм.

Хариулт нь хэтэрхий том байж болох учраас $1000000007$ $(10^{9} + 7)$ модулиар хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
?01???
Гаралт
4
Оролт
?
Гаралт
2
Оролт
**12
Гаралт
0
Оролт
1
Гаралт
0

Тэмдэглэл

Эхний жишээний хувьд дараах зөв талбарууд байж болно: $001**1$, $001***$, $001*2*$, $001*10$.

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