Tree

After a productive day, Serhiy decided to indulge in his favorite pastime—drawing. Naturally, he began by sketching the Main Uzhland Tree. This tree is unique: it has $n$ branches, numbered from $1$ to $n$, arranged in a cycle. This means the branch following the first is the second, the one after the second is the third, and so on, with the branch following the $n$-th being the first again.

Initially, each branch has a certain number of birds perched on it (some branches may have no birds at all). There are $m$ birds in total, numbered from $1$ to $m$. Each bird has a specific weight, calculated as (a_i + b) \bmod (10^9 + 7), where $a$ and $b$ are constants, and x \bmod y denotes the remainder of $x$ divided by $y$. All bird weights are distinct. On branch $i$, there are initially c_i birds, such that branch $1$ has birds numbered 1, 2, \ldots, c_1, branch $2$ has birds numbered c_1 + 1, c_1 + 2, \ldots, c_1 + c_2, and so forth. It is guaranteed that c_1 + c_2 + \cdots + c_n = m.

Every second, the lightest bird from each branch with at least one bird flies to the next branch. For example, if the tree has $3$ branches, and the first branch has birds with weights \{1, 3, 5\}, the second branch has $\{2,7\}$, and the third branch has \{4, 5, 6\}, then after one second, the birds' weights on the branches will be \{3, 4, 5\}, \{1, 7\}, \{2, 5, 6\} respectively. Serhiy is curious about two numbers, $k$ and $t$. He wants to know the weight of the bird that will fly from branch number $k$ at second number $t$.

Task

Write a program that, given the initial distribution of birds on the tree and the numbers $k$ and $t$, determines the weight of the bird that will fly from branch number $k$ at the second number $t$.