2017 Winter Waterloo Local ACM Contest, Problem E
Vera has friends numbered from to . Being in Software Engineering, all her friends do not have enough spare time to engage in relationships. However, friends have crushes on each other.
If is a non-negative integer, let be the number of ones in the binary representation of .
Let , where are integer constants.
It is known that for any 2 friends and where , if is even then has a crush on , otherwise has a crush on .
Vera thinks love triangles are very funny. A love triangle is a set of 3 friends such that has a crush on , has a crush on and has a crush on .
Given integers tell Vera how many love triangles exist among her friends. Two love triangles are different if they contain a different set of friends.
Constraints
- are integers
- is prime
Input Specification
The input will be in the format:
Output Specification
Output one line with the number of love triangles.
Sample Input 1
3 5 3 4
Sample Output 1
1
Explanation of Sample Output 1
Let denote that friend has a crush on friend .
We have , , and . So , , and , so there is one love triangle.
Sample Input 2
3 3 1 2
Sample Output 2
0
Explanation of Sample Output 2
We have , , and , so there are zero love triangles.
Sample Input 3
1337 10007 1337 1337
Sample Output 3
99141170
Comments