是水晶城堡的守护者。城堡的长廊里镶嵌着一排 颗魔法水晶，第 颗水晶的颜色编号为 。长廊中相邻且同色的水晶会产生共鸣，形成一个色段——即极大的连续相同颜色段。例如颜色序列 有 个色段：、 和 。
每天都有旅行者慕名前来，提出 个问题。每个问题指定一段区间 ：如果把这段水晶取下来随机打乱重新排列（所有不同的颜色序列等概率出现），形成的色段数量的期望值是多少？
答案对 取模。即若答案为最简分数 ，输出 。可以证明在本题约束下 总是存在的。
第一行有一个整数 （），表示数据组数。接下来 段，每段描述一组数据：
数据保证 ，。
对于每组数据中的每个询问，输出一行一个整数，表示期望色段数量对 取模的结果。
1 4 2 1 1 2 2 1 2 1 4
1 3
1 10 5 3 5 3 3 6 4 8 2 3 5 6 9 1 8 8 10 4 9 7 7
4 748683272 3 665496241 1
对于第一组样例：
第一个询问，取出的水晶颜色为 ，只有一种排列，色段数为 。
第二个询问，取出的水晶颜色为 。 种排列的色段数分别为 ，期望值为 。
