You are given a string S of length N$.$ The string S consists of only lowercase English letters $($a$,$ b$,$ c$,...,2).$ You are also given an array A of size $26.$ You have to partition the given string into exactly K parts. A partition is called good if it holds the following conditions

$1.$ String S should be partitioned into exactly K contiguous substrings, No substrings can be empty. $2.$ Each partition should contain a maximum A$[0]$ number of occurrences of a$\text{'}$ A$[1]$ number of occurrences of $\text{'}"$ so on A$|25]$ occurrences of z

For example, consider string "aab", and A$|0]=1,$ A$|1]=1$ and K $=2($ a ab is a good partition but aa I b is not a good partition$)$

You are required to count the number of the good partition of string S$.$ Since$\_$the $\_$number of aood partitions $\_$can be verv larae. print modulo