Gülməli rəqəmlərin hesablanması
Hesablamanın asan olduğunu düşünürsünüz? Obyektlərin təbiətini tam başa düşsəniz belə, bu həmişə belə olmaya bilər.
2N-rəqəmli tam ədəd X (bəlkə də başda sıfırlarla) "əyləncəli" adlanır, əgər elə iki N-rəqəmli tam ədəd a və b (bəlkə də başda sıfırlarla) mövcuddursa ki, a + b = 10^N və hər bir rəqəm d üçün S_d(X) = S_d(a) + S_d(b) bərabərliyi doğrudur. Burada S_d(P) (0 ≤ d ≤ 9) - P ədədinin onluq yazılışında rəqəm d-nin daxilolmalarının sayıdır. Məsələn, 46 (4 + 6 = 10^1), 9820 (98 + 02 = 10^2) və 08362090 (6020 + 3980 = 10^4) ədədləri əyləncəlidir.
Cüt uzunluqlu rəqəmlər və sual işarələrindən ibarət bir ardıcıllıq verilir. Sual işarələrini rəqəmlərlə əvəz edərək əyləncəli ədəd əldə etməyin neçə yolu olduğunu tapın. Cavabı 10^9 + 7 modulu ilə hesablayın.
Giriş verilənləri
Yeganə sətir boş olmayan rəqəmlər və sual işarələrindən ibarət ardıcıllıqdan ibarətdir. Ardıcıllığın uzunluğu cütdür və 10^5-dən çox deyil. Sual işarələrinin sayı 1000-dən çox deyil.
Çıxış verilənləri
Axtarılan yolların sayını 10^9 + 7 modulu ilə çıxarın.