Mahmoud wrote a message s of length n. He wants to send it as a birthday PResent to his friend Moaz who likes strings. He wrote it on a magical paper but he was surprised because some characters disappeared while writing the string. That's because this magical paper doesn't allow character number i in the English alphabet to be written on it in a string of length more than ai. For example, if a1?=?2 he can't write character 'a' on this paper in a string of length 3 or more. String "aa" is allowed while string "aaa" is not.

Mahmoud decided to split the message into some non-empty substrings so that he can write every substring on an independent magical paper and fulfill the condition. The sum of their lengths should be n and they shouldn't overlap. For example, if a1?=?2 and he wants to send string "aaa", he can split it into "a" and "aa" and use 2 magical papers, or into "a", "a" and "a" and use 3 magical papers. He can't split it into "aa" and "aa" because the sum of their lengths is greater than n. He can split the message into single string if it fulfills the conditions.

A substring of string s is a string that consists of some consecutive characters from string s, strings "ab", "abc" and "b" are substrings of string "abc", while strings "acb" and "ac" are not. Any string is a substring of itself.

While Mahmoud was thinking of how to split the message, Ehab told him that there are many ways to split it. After that Mahmoud asked you three questions:

Two ways are considered different, if the sets of split positions differ. For example, splitting "aa|a" and "a|aa" are considered different splittings of message "aaa".

The first line contains an integer n (1?≤?n?≤?103) denoting the length of the message.

The second line contains the message s of length n that consists of lowercase English letters.

The third line contains 26 integers a1,?a2,?...,?a26 (1?≤?ax?≤?103) — the maximum lengths of substring each letter can appear in.

Print three lines.

In the first line print the number of ways to split the message into substrings and fulfill the conditions mentioned in the problem modulo 109??+??7.

In the second line print the length of the longest substring over all the ways.

In the third line print the minimum number of substrings over all the ways.

3aab2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1output
322input
10abcdeabcde5 5 5 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1output
40143Note
In the first example the three ways to split the message are:
a|a|baa|ba|ab
The longest substrings are "aa" and "ab" of length 2.
The minimum number of substrings is 2 in "a|ab" or "aa|b".
Notice that "aab" is not a possible splitting because the letter 'a' appears in a substring of length 3, while a1?=?2.
題意：
給你一個長度為n的字符串; 這個字符串只包含小寫字母; 然后讓你把這個字符串進行分割;形成若干個小的字符串; 但是不是任意分割的; 每個小寫字母都有一個數字ma[i];表示這個字母能夠存在于長度不超過ma[i]的字符串內; 
在這個條件下分割; 
這題想出一半吧。。細節還是錯了一些，還是菜。。。就是怎么判斷這個這個單詞是不是每個單詞的長度都符合。。。想寫一個check函數的。。最后模仿q巨的寫法。。
思路：xjbdp，對于每一個字符有兩種來源，一個是自己組成一段，一個是與前面某幾個字符組成一段（老生長談了。。），對于方案數，自己組成一段，方案數就是+= 前i-1的方案數，如果與前面一個字符組成一段，就是+=前i-2，同理與前2個前3個。。判斷這組成一段的字符，是不是每個字符都符合條件，這里用一個limit記錄這一段所有字符中“最短的限制”，其實也就是這一段的限制。。求最長的一段，就是比較當前這一段，跟這一段之前的最大值。。（這里卡了一會，，），求最小的段數，就是這一段之前的+1.。代碼很簡單，看代碼差不多就會了。。
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int maxn = 1e3 + 5;const int Mod = 1e9 + 7;int dp[3][maxn], a[30];char str[maxn];int main(){    int n;    cin >> n;    scanf("%s", str+1);    for(int i = 1; i <= n; i++)    {        dp[1][i] = -1;        dp[2][i] = maxn;    }    for(int i = 0; i < 26; i++)        cin >> a[i];    dp[2][0] = 0;  //下面轉移方程有i-1，所以str從1開始，把0初始化    dp[0][0] = 1;    for(int i = 1; i <= n; i++)    {        int limit = a[str[i]-'a'];  //這里是精髓        for(int j = i; j >= 1; j--)        {            limit = min(limit, a[str[j]-'a']);  //找出每個字符最短的            if(i-j+1>limit) break;  //如果不符合，就跳出，最后一個字符，與后面的幾個組成，不能挎著組合            dp[0][i] = (dp[0][i] + dp[0][j-1]) % Mod;  //一直到跳出，這些都是一些方案            dp[1][i] = max(dp[1][j-1], max(dp[1][i], i-j+1));  //有兩個max，一定要與j-1相比較            dp[2][i] = min(dp[2][i], dp[2][j-1]+1);  //前面的段數+1        }    }    for(int i = 0; i < 3; i++)        cout << dp[i][n] << endl;    return 0;}