Project Euler #156: Counting Digits

_{This problem is a programming version of Problem 156 from projecteuler.net}

Starting from zero the natural numbers are written down in base like this: ....

Consider the digit . After we write down each number , we will update the number of ones that have occurred and call this number . The first values for , then, are as follows:

Note that never equals .

So the first two solutions of the equation are and . The next solution is .

In the same manner the function gives the total number of digits that have been written down after the number has been written.

In fact, for every digit , is the first solution of the equation .

Let be the sum of all the solutions for which .

You are given base and the set of digits in base . Find for numbers written in base .

Note: if, for some , for more than one value of this value of is counted again for every value of for which .

Input Format

First line of each test contains two integers: and - base and the cardinal number of . Second line contains distinct space-separated digits in base .

Constraints

Output Format

Output a single number which is the answer to the problem.

Sample Input

2 1
1

Sample Output

Explanation

There are two solutions where which are and . Starting from .