Кільце

На столі лежить різнокольорове кільце. Воно має $k$ секторів, $i$-ий сектор має колір $i$ (усі $k$ кольорів попарно різні). Сектори послідовно пронумеровані за годинниковою стрілкою. Канга пропонує Малюку Ру написати на кільці $n$ різних цілих чисел від $1$ до $n$. Число $i$ слід написати або на секторі кольору x_i, або на довільному іншому, який знаходиться не далі a_i секторів від x_i проти годинникової стрілки, або не далі ніж b_i секторів за годинниковою стрілкою.

Канга повідомив, що усі числа записані коректно з врахуванням вище наведених умов, у кожному секторі може бути записане не більше одного числа, а числа $1$, $2$, $\dots$, $n$ розміщені за годинниковою стрілкою: якщо почати рух від сектора, на якому записана $1$ за годинниковою стрілкою, то порядок чисел буде $2$, $3$, $\dots$, $n$ і знову $1$.

Малюк Ру хоче знати кількість способів, якими він може пошкодити різнокольорове кільце, записавши на ньому числа у правильному порядку. Щоб пошкодити кільце — не важливо, які числа Ви на ньому пишете.