### Problem Statement

A friend of mine once told me that his phone number, 642-5616, is easy to remember because it is made up of only powers of 2: "64" + "256" + "16". This made me wonder how many numbers of various lengths had this property.

Given ints b and digits, write a method to compute how many integers of the given number of digits can be formed by concatenating various powers of the given base. Use only non-negative powers of the base (including b0, which equals 1).

For example, given b = 12, and digits = 4, there are 8 such numbers:

```    1111: "1" + "1" + "1" + "1"
1112: "1" + "1" + "12"
1121: "1" + "12" + "1"
1144: "1" + "144"
1211: "12" + "1" + "1"
1212: "12" + "12"
1441: "144" + "1"
1728: "1728"
```

### Definition

 Class: StringOfPowers Method: count Parameters: int, int Returns: long Method signature: long count(int b, int digits) (be sure your method is public)

### Constraints

-b will be between 2 and 999999999, inclusive.
-digits will be between 1 and 18, inclusive.

### Examples

0)

 `12` `4`
`Returns: 8`
 This is the example in the problem statement.
1)

 `10` `7`
`Returns: 64`
 The first digit must be a 1, and the remaining 6 digits can each be zero or one. Therefore, there are 26 = 64 possibilities.
2)

 `11` `2`
`Returns: 1`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3006

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5886&pm=3006

legakis

#### Testers:

PabloGilberto , lbackstrom , Yarin , vorthys

#### Problem categories:

Dynamic Programming, Simple Math