prlong longf

Interview

Time limit2sMemory limit1024 MB

Summary

Count the original strings that become the given string when every "int" is replaced with "longlong".

Level: Medium5 of 10
Topics: Dynamic programming, String matching
Solved: No attempts yet

Problem

Seongseo received a Wrong Answer verdict while solving a Bronze 5 problem.

Thinking that the numbers had grown too large and overflowed during the calculation, Seongseo used the editor's Find and Replace to change every int in the code to long long. But every printf was changed to prlong longf as well!

#include <stdio.h>

long long main(){
    long long n, res = 1;
    scanf("%d", &n);
    for(long long i = 1; i <= n; i++){
        res *= i;
    }
    prlong longf("%d\n", res);
    return 0;
}

Tired of fixing the code by hand, Seongseo planned to give the contestants the changed code and ask them to restore the original. Then Seongseo realized that the original code might not be uniquely recoverable from the changed code. Seongseo came up with a good problem idea and set the following problem for 2023 SCON.

You are given a string in which every int has been changed to longlong. How many original strings are possible?

Input

The first line contains the length $N$ of the changed string.

The second line contains the changed string of length $N$ , in which every int has been changed to longlong.

Output

Print the number of possible original strings.

Constraints

$1\leq N\leq 80$
All characters of the given string are lowercase English letters, with no spaces.
The given string does not contain int as a substring.

Examples3

Example 1
Input
```
15
prlonglonglongf
```
Expected output
```
3
```
Example 2
Input
```
15
longestpathtowf
```
Expected output
```
1
```
Example 3
Input
```
22
longlongdoublelonglong
```
Expected output
```
4
```