Incredible! Impossible!#3864
"
textitGive me the sums of each column and of each row of the rectangular table n \times m", — Alex said, — "
textitand I will tell you whether such a table exists, and if it exists for a small fee I can create an example of such a table". "
textitIncredible! Impossible!", — say all his classmates, — "
textitSo many numbers! You must be a true genius!".
But Basil does not like that Alex becomes the most well-known person at the school.
— "
textitI say! I am Basil the greatest! Given a rectangular table n \times m and the sums of rows and columns I will tell you the number of possible tables with non-negative integers satisfying these conditions".
— "
textitYou boast! I bet five dollars you can't do it even for n \times 3", — Alex says.
— "
textitI bet five that I can!", — says Basil.
Tomorrow is the contest. Alex will create some tables with size n \times 3, and tell Basil the sums and the dimensions. All the boys and girls are placing bets on who will be the winner!
You are Alex's friend. He wants to create some hard data sets for Basil, and he needs to have a method to calculate the answer. Because Alex can't solve such kinds of tasks, he asked you to write a program that will do it for him.
Alex needs only the last seventeen digits to check the answers. So you must calculate the number of possible tables taken modulo 10^{17}.
The first line contains four numbers: , c_1, c_2, c_3, where is the number of rows, c_i are the sums of columns. numbers follow, each is the sum of the corresponding row. and all sums are non-negative integers. They are not greater than .
On the first line, output the number of possible tables, taken modulo 10^{17}.
Örnek 1