坂井和奏想要完成当年和母亲没有写完的歌。她找到了不完整的旋律，想将它谱成一首优美和谐的乐曲。
一段旋律的长度为 ，由 种不同音符组成，即每个音符 均为 到 中的一个整数。 种音符构成了一个平均律，相邻两个音符 之间会构成一个大小为 的进行。
和奏有一个进行的和谐度表 ，表示大小为 的进行的和谐度为 。
她认为在一段旋律中，相同大小的进行反复出现时，其和谐度是幂次级叠加的，即若一段旋律中有 个大小为 的进行，则它们总的和谐度为 。特别地，她认为 。
她认为旋律中不同大小的进行之间和谐度是简单叠加的，即整段旋律的和谐度为 。
现在她找到了那份不完整的旋律，其中有 个音符已经确定，分别为 。和奏想请你求出，如果她可以任意选择其余 个音符，得到的 种不同旋律的和谐度之和是多少。由于答案可能很大，你只需要帮她求出其对 取模的值。
