Coding

Interview

Time limit1sMemory limit1024 MB

Summary

Count how many distinct strings result from replacing some non-overlapping adjacent digit pairs (values 10 to 10+n-1) with letters a to z.

Level: Medium5 of 10
Topics: Dynamic programming, String, Combinatorics, Hash map
Solved: No attempts yet

Problem

You are given a string made of the digits '0' through '9'. We encode it by replacing some pairs of consecutive digits with a lowercase letter of the Latin alphabet according to the following rule: 10 → 'a', 11 → 'b', 12 → 'c', …, 34 → 'y', 35 → 'z'. For example, in the string "1234" we can replace the first pair of digits with the letter corresponding to 12, obtaining "c34". We can also replace the pair "23" with the letter "n", obtaining the encoding "1n4". If we replace both consecutive pairs of digits, we obtain "cy".

Write a program code that counts the number of distinct strings that can be obtained by encoding a given digit string in this way using the first n lowercase letters of the Latin alphabet. For example, when n = 5, we use the letters 'a', 'b', 'c', 'd', and 'e'. When n = 0, we use no letters in the encoding.

Input

The first line contains the integer n. The second line contains the given string.

Output

Print one integer equal to the requested count.

Constraints

0 ≤ n ≤ 26; the given string consists of digits and its length is at most 50.

Examples3

Example 1
Input
```
0
10237
```
Expected output
```
1
```
Example 2
Input
```
1
10237
```
Expected output
```
2
```
Example 3
Input
```
26
10237
```
Expected output
```
4
```