Ağac

Sərgi işi bitirdikdən sonra sevimli məşğuliyyəti olan rəsmlə məşğul olmağa qərar verdi. Əlbəttə ki, əvvəlcə Baş Ujland Ağacını çəkdi. Bu ağac xüsusidir: $n$ budaqdan ibarətdir və budaqlar $1$-dən $n$-ə qədər nömrələnib, dövrü şəkildə yerləşir. Yəni birinci budaqdan sonra ikinci, üçüncü və s. gəlir, ən sonuncu ($n$-ci) budaqdan sonra isə yenidən birinci budaq gəlir.

İlkin olaraq hər budaqda müəyyən sayda quş var (bəzən heç bir quş olmaya da bilər). Ağacda cəmi $m$ quş var, onların hamısı $1$-dən $m$-ə qədər nömrələnib. Hər quşun çəkisi belə hesablanır: (a_i + b) \bmod (10^9 + 7), burada $a$ və $b$ sabitlərdir, x \bmod y isə $x$-in $y$-ə bölünməsindən qalan qalığı göstərir. Bütün quşların çəkiləri fərqlidir. $i$-ci budaqda ilkin olaraq c_i quş var, belə ki, birinci budaqda 1, 2, \ldots, c_1, ikinci budaqda c_1 + 1, c_1 + 2, \ldots, c_1 + c_2 və s. quşlar oturur. c_1 + c_2 + \cdots + c_n = m şərti təmin olunur.

Ə hər saniyə, hər budaqda ən azı bir quş olduqda, çəkisi ən az olan quş növbəti budağa uçur. Məsələn, ağacın $3$ budağı varsa, ilk budaqda \{1, 3, 5\} çəkili quşlar, ikinci budaqda $\{2,7\}$ və üçüncü budaqda \{4, 5, 6\} çəkili quşlar varsa, bir saniyədən sonra budaqlardakı quşların çəkiləri uyğun olaraq \{3, 4, 5\}, \{1, 7\}, \{2, 5, 6\} olacaq. Sərgini iki rəqəm maraqlandırır: $k$ və $t$. O, $k$-cı budaqdan $t$-ci saniyədə uşacaq quşun çəkisini bilmək istəyir.

Tapşırıq

Ağacdakı quşların ilkin yerləşməsi və $k,t$ rəqəmləri verilib. $k$-cı budaqdan $t$-ci saniyədə uşacaq quşun çəkisini tapın.