This problem is a programming version of Problem 217 from projecteuler.net
Fix an integer .
A positive integer with digits (in base ) is called -balanced if its first digits sum to the same value as its last digits when written in base , where (ceiling of ) is the smallest integer , thus and .
Examples:
- All palindromes (in base ) are -balanced.
- For , and are -balanced.
- For , and are both -balanced.
You will be given , and an integer , find the number and the sum of all -balanced integers .
Print your answers modulo .
Input Format
The first line of each test file contains two space-separated integers and .
The next line contains space-separated integers (in this order), the digits of the integer in base .
Constraints
- .
- .
- .
- .
Output Format
Print two space-separated integers in one line, denoting the number and the sum in question.
Sample Input 0
10 1
7
Sample Output 0
7 28
Explanation 0
The set of -balanced integers is
Sample Input 1
11 3
1 10 9
Sample Output 1
31 2662
Explanation 1
The number given is equal to when converted to base .
The set of -balanced integers is (when converted to base )
Sample Input 2
10 4
4 8 5 7
Sample Output 2
378 876573