. then makes subsequences of the string by deleting a non-negative number of characters from , but not changing their order. Note that subsequences are distinct if the set of their deleted indices are different, and a subsequence must have a positive length. She then goes to the store to buy all the string decorations for each subsequence. However, because the shop she bought the strings from is ~~cursed~~ magical, any string she puts on the 🎄 will cause it to collapse if its remainder is not modulo . How many strings can decorate her 🎄 with such that it doesn't collapse? Because wants to put many decorations on her 🎄, please give the answer modulo .

#### Input Specification

The first line will contain .

The next line will contain the string , where only contains numeric characters.

#### Output Specification

Output the number of strings can put on her 🎄, modulo .

#### Subtasks

##### Subtask 1 [30%]

##### Subtask 2 [70%]

No further constraints.

#### Sample Input

```
5 3
32123
```

#### Sample Output

`2`

#### Explanation for Sample

The subsequences in question are and .

## Comments