小红定义一个字符串的权值为，该字符串包含的 子序列 的数量。 现在小红拿到了一个由字符 和 组成的字符串环（即最后一个字符下一个是第一个字符）。现在小红想知道，这个环的所有长度不小于 的连续子串权值之和是多少？ 由于答案可能很大，请将答案对 取模后输出。 子序列为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串，字符串恰好为 。 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。在本题中，环上的子串为，任取两个下标 和 ，从 不断向右取直到 形成的连续子串；特殊的，若 ，则会从 向右取到最后一个字符，之后从第一个字符取到 。

输入描述:

第一行输入一个正整数 代表字符串的长度。 第二行输入一个长度为 、由字符 和 构成的字符串 。

输出描述:

输出一个整数，代表所有长度不小于 的连续子串的权值之和。由于答案可能很大，请将答案对 取模后输出。