Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

matrices

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
E2. Trails (Medium)

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHarry 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$$$.

Input

The first line contains the integers $$$m$$$ and $$$n$$$.

The second line contains $$$m$$$ integers, $$$s_1, \dots, 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, \dots, l_m$$$, where $$$l_i$$$ is the number of long trails between cabin $$$i$$$ and Lake Geneva.

We have the following constraints:

$$$0 \le s_i, l_i \le 10^3$$$.

$$$1 \le m \le 10^2$$$.

$$$1 \le n \le 10^9$$$.

Output

The number of possible combinations of trails, modulo $$$10^9 + 7$$$.

Example

Input

3 21 0 10 1 1

Output

18

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/24/2024 01:53:40 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|