小 W 收到小 P 的棒棒糖的图之后觉得这实在是太棒棒糖了，于是回馈了一条不那么棒棒糖的彩丝带。
小 W 给彩丝带上点明暗，让它更加美丽。
对于一条由 个格子组成的彩丝带，定义将彩丝带染成长度为 的明暗序列 的染色难度 为：
初始，彩丝带上每个格子暗度均为 。
你可以进行若干次操作，每次操作你需要：
表示最少需要几次操作，才能使得所有 的位置的暗度 ，且所有 的位置的暗度恰好为 。
现在小 W 有一个长度为 的彩丝带与一个长度为 的备选明暗序列 。他还没有想好怎样的明暗最好看，于是他希望你对于所有 的子区间 ，将 个格子组成的彩丝带染色的难度之和。形式化地讲，你需要求出 。
答案对 取模输出。
第一行一个正整数 。
接下来一行 个非负整数 。
一个非负整数表示答案对 取模后的结果。
3 1 0 2
9
6 2 0 1 3 0 1
51
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
993
对于所有数据：。
