Arrays Sum

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
You are given an array A, consisting of N integers and an array B, consisting of M integers.
The subsequence of A is the array that can be obtained by picking the elements at the arbitrary sorted set of positions from A.
Your task is to count the number of such subsequences C of A that:
 C contains exactly M elements.
 The array (C+B) is nondecreasing. Here by + operation, we mean elementwise sum.
For example, the array (4, 8, 5) plus the array (10, 20, 30) is (14, 28, 35).
Formally, (C+B) is an array of size M such that (C+B)_{i} = C_{i} + B_{i}.
In case some subsequence appears more that once, you should counts it as many times as it appears.
Formally, two subarrays of an array a, (a_{i_1}, a_{i_2}, ... ,a_{i_n}) and (a_{j_1}, a_{j_2}, ... ,a_{j_m}) will be considered different if either their lengths are different i.e. n != m or there exists an index k such that such that i_k != j_k.
Since the answer can be very large, we ask you to calculate it, modulo 10^{9}+7.
Input
The first line of input contains a pair of space separated integers N and M, denoting the number of elements in the array A and the number of elements in the array B.
The second line contains N spaceseparated integers A_{i}, denoting the array A.
The third line contains M spaceseparated integers B_{j}, denoting the array B.
Output
Output a single line containing the number of subsequences C as asked in the problem, modulo 10^{9}+7.
Constraints
 1 ≤ A_{i}, B_{i} ≤ 10^{9}
 1 ≤ M ≤ N
Subtasks
 Subtask #1 (33 points): 1 ≤ N ≤ 50, 1 ≤ M ≤ 5
 Subtask #2 (33 points): 1 ≤ N ≤ 500, 1 ≤ M ≤ 50
 Subtask #3 (34 points): 1 ≤ N ≤ 2000, 1 ≤ M ≤ 1000
Example
Input #1: 5 3 1 5 2 4 7 7 9 6 Output #1: 4 Input #2: 4 2 7 7 7 7 3 4 Output #2: 6
Explanation
Example case 1. The suitable subsequences are (1, 2, 7), (1, 4, 7), (5, 4, 7), (2, 4, 7).
Example case 2. The suitable subsequence is (7, 7), and it appears 6 times:
 at indices (1, 2)
 at indices (1, 3)
 at indices (1, 4)
 at indices (2, 3)
 at indices (2, 4)
 at indices (3, 4)
So, the answer is 6.
Author:  xcwgf666 
Tester:  zedthirtyeight 
Editorial  http://discuss.codechef.com/problems/ARRAYSUM 
Tags  datastructure, dynamicprogramming, ltime34, mediumhard, xcwgf666 
Date Added:  21022016 
Time Limit:  1  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 