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
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.