Jinwoo's Password

Interview

Time limit1sMemory limit256 MB

Summary

Given N and a lowercase password of length at most N, find its 1-based position among all strings of length 1 to N in lexicographic order.

Level: Medium4 of 10
Topics: String, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

Jinwoo is very forgetful, so he often forgets the passwords for the websites he has signed up for. To prepare for this, Jinwoo creates passwords using only lowercase English letters. Whenever he forgets a password, he tries the strings that could be the password in lexicographic order until he finds the correct one. A string that could be the password is any string consisting only of lowercase English letters whose length is between 1 and N, inclusive. (N is the maximum password length allowed by the website Jinwoo signed up for.) Because he uses this method, it is very important to know how long it will take Jinwoo to guess the password when he forgets it. Jinwoo types very slowly, so trying one password takes 1 second.

Jinwoo has forgotten his password again. Calculate how many seconds it will take before he guesses his password.

Input

The first line of the input gives N (1 ≤ N ≤ 10), the maximum length of the password. The second line gives Jinwoo's password.

Jinwoo's password consists only of lowercase English letters, and its length is between 1 and N, inclusive.

Output

Print how many seconds it takes for Jinwoo to guess his password when the strings that could be the password are tried in lexicographic order.

Examples3

Example 1
Input
```
3
ba
```
Expected output
```
705
```
Example 2
Input
```
6
b
```
Expected output
```
12356632
```
Example 3
Input
```
10
zzzcaaaauu
```
Expected output
```
146806068942309
```