Two Dinosaurs

Description

Once upon a time, there were two dinosaurs - Raphael and Leonardo, they were really good friends, and they liked food . For each meal, they would go to a forest and each would eat N types of food (e.g. fruits, leaves, other animals...). The calories absorbed from each type of food for them could be different, and can be denoted by two arrays, A and B. A_i,B_i (i=0...N-1) denotes respectively the calories that Raphael and Leonardo will get if they consume the i^th food. They can eat all types of food as long as they want. However, both of them do not want to become fatter than the other. Therefore, for each meal one of them will not consume more than Q calories than the other. For each type of food, the calories that can be absorbed by the two dinosaurs could be either the same or different.

Endpoint

Provide a POST endpoint /two-dinosaurs that given 1 set of input will return 1 set of output

Input

The HTTP POST request will come with a body of Content-Type: application/json .

{
    "number_of_types_of_food" : N,
    "calories_for_each_type_for_raphael" : A,
    "calories_for_each_type_for_leonardo" :  B,
    "maximum_difference_for_calories" : Q
}

Output

The expected HTTP response will come with a body of Content-Type: application/json containing

{
    result : (The total number of combinations)
}

Limits

• 1 ≤ N ≤ 200
• 0 ≤ A_i, B_i ≤ 2,000
• 0 ≤ Q ≤ 200,000
• HTTP request timeout: 20s
• As the number of combinations can be huge , please return the result modulo 100,000,123 .

Sample

Input

{
    "number_of_types_of_food" : 2,
    "calories_for_each_type_for_raphael" : [4,5],
    "calories_for_each_type_for_leonardo" :  [3,6],
    "maximum_difference_for_calories": 3
}

Output

{
    "result" : 8
}

Explanation

There are 8 ways to get an absolute calories difference less than or equal to 3 :

Raphael : {0 , 0} Leonardo: {0 , 0} i. e. Both eat none of the food

Raphael : {4 , 0} Leonardo: {0 , 6} i. e. Raphael eats only the first type of food and Leonardo eats only the second type.

Raphael : {0 , 0} Leonardo: {3 , 0}

Raphael : {0 , 5} Leonardo: {3 , 0}

Raphael : {0 , 5} Leonardo: {0 , 6}

Raphael : {4 , 0} Leonardo: {3 , 0}

Raphael : {4 , 5} Leonardo: {3 , 6}

Raphael : {4 , 5} Leonardo: {0 , 6}