一个字符串的权值被定义为该字符串包含的"lnc"子串个数。例如"lnclncc"的权值是 ，lnc的权值是 ，但是"lcncl"的权值是 ，因为它的所有子串都不为"lnc"。
现在， 从 处收到了一个仅包含'l','n','c'三种字符的字符串用于表达他对 的爱意。
对 的爱意是这个字符串的所有子序列代表的字符串的权值之和。你想知道 到底有多爱 ，于是你决定计算一下这个权值和。由于 可能非常喜爱 ，该数字可能非常大。所以，你只需要将答案对 取模并输出。
注：一个长度为 的字符串的子序列可以为空，所以共有 个。