橘子洲的烟花我吹爆！
橘子洲又开始放烟花！可是究极卷王马老师错过了，机房里的菜鸡们想让马老师重新看到这场烟花，于是创造了 种烟花模拟机。
每一种烟花模拟器，可以模拟出一场烟花，用只有 的字符串 表示。 可以理解为这场烟花共 个时刻，每个时刻 会模拟出 类型的烟花，启动一次需要 ，每次启动可以在任意时刻，也可以在任意时刻关闭。也就是说，我们可以用代价模拟一场 的某个子串代表的烟花。
菜鸡们想还原橘子洲的烟花，这场烟花可以用 表示，但又希望代价最少。同时，新创造的烟花模拟器容易出bug，所以他希望你告诉他，在代价最少的情况下，有多少种烟花模拟器启动方式。方案数对 取模。
两种不同的启动方式 定义为：存在烟花模拟器种类使用方案不同，或在使用同一种烟花模拟器时持续的时间不同。
注意：使用同一种烟花模拟器，即使开始和结束时间不同，只要持续时间相同，就算同一种方案。
