shivam-shantam-and-their-absolute-difference-3

"Sometimes the thing that brings us together also pulls us apart."  - Jarod Kintz.
Shivam and Shantam are really good friends. What mostly brings them together is the hours of group study they have done in the two years of their engineering, and there is only more to add to this. They both start studying together for exams , and keep explaining topics and clearing each other's slightest of doubts.

But , unfortunately , marks and money can always make or break relations. Both of them have to answer N questions in tomorrow's paper. We also have two arrays , A and B. Ai denotes the marks Shivam will get if he answers the i^th question. Bi denotes the marks Shantam will get if he answers the i^th question. The person not choosing to answer the question would get no marks.

Obviously , there are many ways in which they can give their papers. Let the final score of Shivam be S and that of Shantam be K. We are interested in knowing the number of ways such that the absolute difference in S and K is less than or equal to Q.

Input Format :

The first line contains N , the number of questions. The next line contains N space separated integers denoting Ai , the marks that Shivam can score if he attempts the i^th question. The next line contains N space separated integers denoting Bi , the marks that Shantam can score if he attempts the i^th question. The next line contains Q , the maximum allowed absolute difference.

Output Format :

Since the number of ways can be huge , output the answer modulo 10^9 + 7 in a separate line.

Contraints :
1 ≤ N ≤ 200
0 ≤ Ai, Bi ≤ 2 * 10^3
0 ≤ Q ≤ 10^6

SAMPLE INPUT
2
1 2
4 5
2

SAMPLE OUTPUT
6

Explanation

There are 6 ways to get an absolute difference less than equal to 2 :
Shivam :  {1 , 0}   Shantam:  {0 , 0} i. e. Shivam answers only the first question, but Shantam answers none.    
Shivam :  {0 , 2}   Shantam:  {0 , 0} i. e. Shivam answers only the second question, but Shantam answers none.    
Shivam :  {0 , 2}   Shantam:  {4 , 0}  
Shivam :  {1 , 2}   Shantam:  {4 , 0}
Shivam :  {1, 2}   Shantam:  {0 , 5}
Shivam :  {0 , 0}   Shantam:  {0 , 0}

Source: hackerearth | Difficulty: MEDIUM


Solutions: