B'Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are m cabins, numbered 1 to m . Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin i is connected with s_i short trails and l_i long trails to the lake. Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the m cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short. How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for n days? Give the answer modulo 10^9 + 7 . The first line contains the integers m and n . The second line contains m integers, s_1, ... , s_m , where s_i is the number of short trails between cabin i and Lake Geneva. The third and last line contains m integers, l_1, ... , l_m , where l_i is the number of long trails between cabin i and Lake Geneva. We have the following constraints: 0 <= s_i, l_i <= 10^3 . 1 <= m <= 10^5 . 1 <= n <= 10^9 . The number of possible combinations of trails, modulo 10^9 + 7 . '...