Козак Вус та кольори
Нещодавно Козак Вус знайшов каменів, розташованих у ряд. Також в нього є різних фарб пронумерованих від до .
Козак Вус хоче розфарбувати камені так, щоб не було двох сусідніх каменів з однаковим кольором. На жаль, деякі камені вже розмальовані.
Козаку Вусу цікаво скільки існує способів розфарбувати ці камені, щоб виконувалась умова вище. При чому не можна перефарбовувати вже розмальовані камені.
Оскільки відповідь може бути дуже великою, то виведіть її остачу від ділення на .
Giriş verilənləri
Перший рядок містить два цілі числа та () — кількість каменів та кількість кольорів.
Другий рядок містить цілих чисел () — кольори каменів. Якщо , то це означає, що відповідний камінь ще не розфарбований. Якщо , то це означає, що камінь розфарбований в колір під номером .
Çıxış verilənləri
Виведіть єдине число — кількість розфарбувань каменів по модулю .
Nümunələr
Qiymətləndirmə
( балів): ;
( балів): ;
( бали): ;
( балів): ;
( балів): без додаткових обмежень.