“呜哇——！怎么会有这么奇怪的数组啊！”
克露丝卡尔酱盯着黑板上写满的 和 ，整个人都不好了。
“前辈前辈！”后辈拽着她的袖子，“如果给你一个区间，里面的数字可以随便重新排列，那有多少种排法能让所有连续子段的乘积加起来正好等于 呢？”
面对那双闪闪发亮的眼睛，克露丝卡尔酱只能硬着头皮接下了这个挑战。
唉，今天的社团活动，似乎又不太平静呢……
给定长度为 的数组 ，每个元素都是 之一。
给定常数 以及 次询问，每次询问指定 ，计算：假如你可以任意排列 下标范围内的元素，有多少种排列方式，使得新数组（长度仍为 ）的所有非空子段乘积之和（即 ）为 。结果对 取模。
注意：即使两个不同的排列得到的数组完全相同，也将它们视为不同的排列。
