This problem is a programming version of Problem 242 from projecteuler.net
Given the set , we define as the number of its -element subsets whose sum of elements is congruent to modulo . For example, , since the set has four -element subsets having an odd sum of elements, i.e.: , , and .
Given integers , , , and , find modulo .
Input Format
The only line of each testfile contains five space-separated integers: , , , and .
Constraints
- .
- .
- .
- For each positive divisor of : .
- .
- The largest prime factor of is less than .
Output Format
Print a single integer denoting
Sample Input 0
20 12 20 10 243
Sample Output 0
63
Sample Input 1
6 0 40 28 1024
Sample Output 1
758
Sample Input 2
74 4 75 3 638976
Sample Output 2
67562
Sample Input 3
999952 976999 716281831 594438575 4559755227955200000
Sample Output 3
1709908210483200000