The Botanist's Growth Notation

A botanist models plant growth with letters. She starts from the string seed. In one generation every letter c that has an entry in rules is replaced, all at the same time, by the string rules[c]. Letters with no entry stay as they are.

After gens generations, return how many copies of the letter target appear among the first k letters of the string. If the string has fewer than k letters, count the whole string.

Examples

Input:  seed = "a", rules = {"a": "ab", "b": "a"}, gens = 4, k = 6, target = "b"
Output: 2
Explanation: a -> ab -> aba -> abaab -> abaababa. The first 6 letters are "abaaba".

Input:  seed = "xa", rules = {"a": "axa"}, gens = 2, k = 100, target = "x"
Output: 4
Explanation: xa -> xaxa -> xaxaxaxa (x has no rule). Only 8 letters exist, 4 are x.

Constraints

• 1 <= len(seed) <= 20; seed, target and all rule strings use lowercase letters
• every value in rules has length 1 to 6
• 0 <= gens <= 100, 0 <= k <= 10**18
• The string can have far more than 10**18 letters, so it cannot be built.

Goals

• Describe a huge generated string by the lengths and letter counts of its pieces
• Memoise (letter, generations) summaries so each is computed once
• Descend into only the one piece that the prefix boundary cuts through