Лаборатория
(Время: 2 сек. Память: 32 Мб Сложность: 88%)
Алексей работает в лаборатории неорганической химии и исследует быстрые реакции обмена лигандами в растворах переходных металлов. В ходе экспериментов он изучает три взаимопревращающиеся формы «Extra» молекулы. В присутствии катализатора в растворе происходит быстрый обмен лигандами. Экспериментально установлено следующее правило взаимодействия между двумя микрокаплями раствора: если в обеих каплях находится одна и та же форма, обмен лигандами не приводит к заметному изменению – состав остаётся прежним, а если формы «Extra» молекулы разные, то быстрый обмен лигандами приводит к тому, что в обеих каплях образуется третья форма, отличающаяся от исходных двух.
Алексей проводит эксперимент на микрофлюидном чипе. На чипе расположены N микрокапель раствора, образующих замкнутое кольцо. Каждая капля содержит одну из трёх указанных форм. Один экспериментальный цикл состоит из серии быстрых контактов между соседними каплями: сначала взаимодействуют капли 1 и 2, затем капли 2 и 3,затем капли 3 и 4, …наконец, капли N и 1. Каждое взаимодействие происходит мгновенно и изменяет состав обеих капель согласно описанному правилу. Такие циклические эксперименты позволяют изучать устойчивость сетей обмена лигандами и динамику промежуточных состояний. Для анализа результатов Алексею нужно знать, каким будет распределение форм после K полных циклов.
Входные данные
В первой строке входного файла INPUT.TXT содержится два натуральных числа N, K (2 ≤ N ≤ 106; 1 ≤ K ≤ 109). Во второй строке расположены N микрокапель раствора в виде строки из цифр 1, 2, 3.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 2
12323 | 33113 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
