Кодовий замок
"Алі-Баба і сорок розбійників"
Всім відома історія про те, як Алі- Баба підслухав фразу, яка відкривала двері в скелі, завдяки чому зміг проникнути в лігво розбійників. Однак мало хто знає про те, що доступ до скарбниці, де вони зберігали награбовані багатства, перебував під механічним кодовим замком, на якому код набирався допомогою N коліщаток. На кожному з них можна за допомогою обертання встановити одну з цифр від 0 до 9. При цьому деякі коліщатка були заклинені на якийсь цифрі і не оберталися. Алі- Баба знав лише те, що в правильному коді сума будь-яких k цифр, що йдуть поспіль, повинна бути однаковою і рівною S.
Ваше завдання - визначити скільки різних комбінацій повинен був перевірити Алі-Баба, щоб відкрити скарбницю.
Вхідні дані
У першому рядку задаються три цілих числа: N, k и S (1 ≤ N ≤ 100, 1 ≤ k ≤ 6, 0 ≤ S ≤ 100.) У другому рядку записані N символів без пробілів, кожен з яких позначає стан відповідного коліщатка. Символ «?» вказує, що коліщатко справно і на ньому може бути встановлена будь-яка цифра, а будь-який цифровий символ позначає, що коліщатко заклинило і на ньому набрана відповідна цифра.
Вихідні дані
У єдиний рядок виведіть одне ціле число - кількість комбінацій цифр, які можуть бути набрані на замку, таким чином, щоб сума будь-яких k цифр, що йдуть поспіль, дорівнювала S.