Problem Name — Separate It

### Statement

You are given an array $$$a$$$ containing $$$n$$$ elements and another array $$$b$$$ containing $$$m$$$ elements. ( Both are 0 indexed ) You want to separate $$$a$$$ into $$$m$$$ non-empty contiguous subarrays, such that each element belongs to exactly one subarray.

Also, the sum of elements of $$$r$$$th subarray ( $$$0 \le r < m$$$ ) should be divisible by $$$b_r$$$.

Find the total number of way to seperate $$$a$$$ into $$$m$$$ subarrays fulfilling the given conditions, modulo $$$10^9 + 7$$$

### Input Format

$$$n$$$ $$$m$$$

$$$a_0 \; a_1 ... a_{n-1}$$$

$$$b_0 \; b_1 ... b_{m-1}$$$

First line contains two space separated integers $$$n$$$ and $$$m$$$.

Second line contains $$$n$$$ space separated integers denoting array $$$a$$$.

Third line contains $$$m$$$ space separated integers denoting array $$$b$$$.

### Constraints

$$$1 \le n \le 10^3$$$

$$$1 \le m \le 10^3$$$

$$$1 \le a_i \le 10^9$$$, where $$$0 \le i < n-1$$$

$$$1 \le b_i \le 10^9$$$, where $$$0 \le i < m-1$$$

### Examples

**Sample Input Output**

Source — Infosys Coding Round on 21st Jan.

I have tried a lot and I was only able to come up with a $$$O(n \cdot n \cdot m)$$$ approach using DP, but couldn't optimize further.

If anyone has any idea how to solve it, or knows any similiar problem, please help.