Time limit: 1.5s
Memory limit: 128MB
Input:
Output:
Task
An array is given with elements and one number . Find out in how many ways we can choose positions from array so that and the sum of the values from array, from this distinct positions, will be multiple of .
Input data
On the first line you will find integers, and .
On the second line you will find numbers, representing the given array.
Output data
On the first line will find a single integer, the number of ways to choose distinct positions in the array so that their sum is multiple of . As the number may pass the long long limit, we will display the number modulo .
Constraints and clarifications
- The values from array
- For points
Comment
Due to the very large input data, we recommend using the following lines at the beginning of the main()
function in the C++ program:
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
Example
stdin
5 3
1 2 3 4 5
stdout
4