Time Limit: 2s
Memory Limit: 256MB
For a string S, define count(S, k) to be the number of occurrences of the symbol k in S. For example, count(bbcac, b) = 2 and count(bbcac, a) = 1.
A prefix of a string S is any string obtained from S by deleting some (possibly none) of the trailing characters of S. For example, the prefixes of acb are the empty string, a, ac, and acb.
A string S has "nice prefixes" if for every prefix P of S and for every two characters k1 and k2 in the alphabet, |count(P, k1) - count(P, k2)| <= 2. For example, bbcac has nice prefixes, but abbbc does not because count(abbb, b) = 3 and count(abbb, c) = 0.
Count the number of strings of length L on an alphabet of size K that have nice prefixes. This number can be large, so print its remainder when divided by 1000000007.