Клітинний автомат

Клітинний автомат — це набір клітин на сітці певної форми, що розвивається через дискретні часові кроки відповідно до правил, які визначають новий стан клітини на основі станів сусідніх клітин. Порядок клітинного автомата — це кількість клітин, які він містить. Клітини автомата порядку $n$ нумеруються від $1$ до $n$.

Порядок клітини — це кількість різних значень, які вона може мати. Зазвичай значення клітини порядку $m$ вважаються цілими числами від $0$ до m-1.

Однією з основних характеристик клітинного автомата є тип сітки, на якій він функціонує. У цій задачі ми розглядаємо особливий вид клітинного автомата — круговий клітинний автомат порядку $n$ з клітинами порядку $m$. Ми будемо позначати такий автомат як $n,m$-автомат.

Відстань між клітинами $i$ та $j$ в $n,m$-автоматі визначається як \min(|i-j|, n-|i-j|). $d$-оточення клітини — це набір клітин, що знаходяться на відстані не більше ніж $d$.

На кожному $d$-кроці значення всіх клітин одночасно замінюються новими значеннями. Нове значення клітини $i$ після $d$-кроку обчислюється як сума значень клітин, що входять до $d$-оточення клітини $i$, за модулем $m$.

Наступне зображення демонструє $1$-крок $5,3$-автомата.

Завдання полягає в обчисленні стану $n,m$-автомата після $k$ $d$-кроків.