Дерево

Після гарного дня Сергій вирішив зайнятися своїм улюбленим хобі — малюванням. Звичайно, спочатку він намалював Головне Ужлянське Дерево. Це дерево особливе: воно має $n$ гілок, пронумерованих від $1$ до $n$, розташованих по циклу. Тобто після першої гілки йде друга, після другої — третя і так далі, а після $n$-ї гілки знову перша.

Спочатку на кожній гілці знаходиться певна кількість пташок (іноді гілка може бути порожньою). Всього на дереві $m$ пташок, пронумерованих від $1$ до $m$. Кожна пташка має вагу, яка обчислюється як (a_i + b) \bmod (10^9 + 7), де $a$ і $b$ — це константи, а x \bmod y — це залишок від ділення $x$ на $y$. Ваги всіх пташок різні. На гілці $i$ спочатку знаходиться c_i пташок, тобто на гілці $1$ сидять пташки 1, 2, \ldots, c_1, на гілці $2$ — c_1 + 1, c_1 + 2, \ldots, c_1 + c_2 і так далі. Гарантується, що c_1 + c_2 + \cdots + c_n = m.

Щосекунди на кожній гілці, де є хоча б одна пташка, на наступну гілку перелітає пташка з найменшою вагою. Наприклад, якщо дерево має $3$ гілки, на першій — пташки з вагами \{1, 3, 5\}, на другій — $\{2,7\}$, а на третій — \{4, 5, 6\}, то за секунду ваги на гілках стануть \{3, 4, 5\}, \{1, 7\}, \{2, 5, 6\} відповідно. Сергія цікавлять два числа $k$ і $t$. Він хоче дізнатися вагу пташки, яка перелетить з гілки $k$ у $t$-ту секунду.

Завдання

Напишіть програму, яка за початковим розміщенням пташок на дереві і числами $k$ та $t$ визначить вагу пташки, що перелетить з $k$-ї гілки у $t$-у секунду.