You are ordering a cake to celebrate the New Year. You have to decide the numbers of decoration items to be topped on the cake. Available items are dog figures, cat figures, red candies, and blue candies.
You want all four items to decorate the cake, and all the numbers of the four items to be different from each other. You also want the number of figures (the sum of dogs and cats) to be within a certain range.
An extra charge for the decoration items is added to the price of the cake. The extra is, although quite queer, the product of the numbers of the four decoration items. You want the cake to look gorgeous as far as the budget allows. Thus, you are not satisfied with a decoration if you can add any of the four items without violating the budget constraint.
The conditions stated above are summarized as follows. Let , , , and be the numbers of dog figures, cat figures, red candies, and blue candies, respectively. All these numbers should be different positive integers satisfying the following conditions for given , , and :
,
,
,
,
, and
.
More than one combination of four numbers of decoration items may satisfy the conditions. Your task is to find how many such combinations exist.
输入格式
The input consists of a single test case of the following format.
Here, , , and are integers appearing in the conditions stated above. They satisfy and .
输出格式
Output the number of combinations of four numbers of decoration items that satisfy the conditions stated above modulo a prime number .
样例
样例输入 1
24 4 6
样例输出 1
12
样例输入 2
30 5 6
样例输出 2
4
样例输入 3
30 9 20
样例输出 3
0
样例输入 4
100000000000000 1 100000000000000
样例输出 4
288287412
数据范围与提示
For Sample Input 2, four combinations of , , , and satisfy all the conditions. is not eligible because its extra cost for the decoration items does not exceed even after adding one more cat figure. is also ineligible because does not hold.
