- All Contests
- ProjectEuler+
- Project Euler #217: Balanced Numbers

# Project Euler #217: Balanced Numbers

# Project Euler #217: Balanced Numbers

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
```