{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Захар Яковлев \\
         Разработка: & Захар Яковлев \\
     \end{tabular}
}

Про эту задачу удобнее думать в терминах графа: дан цикл размера $n$ и $m$ непересекающихся ребер-хорд. Необходимо покрасить вершины в $k$ цветов так, чтобы никакие две вершины, соединенные ребром, не были одного цвета. 

Заметим, что цикл эквивалентен отрезку с проведенным ребром из $1$ в $n$, поэтому далее будем рассматривать задачу на отрезке.

Решим для начала задачу о количестве способов раскрасить ``бамбук'' без исходящих ребер. Для этого зафиксируем цвета на его концах. При этом вся информация задается двумя различными числами: количеством способов раскрасить отрезок так, чтобы оба конца были одинаковыми или различными. При рассмотрении двух последовательных отрезков, граничащих по вершине, достаточно перебрать цвет вершины на границе этих отрезков: он может совпадать с цветом одного из оставшихся концов отрезков или иметь новый цвет. При этом сам по себе цвет промежуточной вершины значения не имеет, а важно только количество возможных цветов. Тогда количество способов покрасить вершины пути из ребер можно посчитать с помощью двоичных подъемов за $O(\log n)$.

Теперь осталось учесть наличие хорд. Для этого заметим, что замыкание пути в цикл приводит лишь к обнулению количества способов раскраски, при которой два противоположных конца имеют равный цвет.

Оказывается, описанных выше операций достаточно для полного решения задачи. Действительно, будем рассматривать непрерывные отрезки в порядке вложенности от меньшего к большему. Тогда мы последовательно будем вычислять количество способов покраски для пути из ребер, замыкания в цикл и объединения двух последовательных отрезков. При этом при рассмотрении в таком порядке в любой момент все ребра на текущем отрезке будут приняты во внимание, и не будет исходящих наружу ребер.

Осталось домножить ответ на количество способов выбрать цвета вершины $1$ и вершины $n$: $k(k-1)$.

Асимптотика работы алгоритма~--- $O(m\log m)$ операций для сортировки отрезков и $O(m\log n)$ для вычисления количества способов раскраски путей. Общая сложность работы алгоритма $O(m\log m + m\log n)$.