小象涂色（elephant.cpp）

时限：$1$ 秒。内存限制：$256$ M。

问题描述

小象喜欢为箱子涂色。小象现在有 $c$ 种颜色，编号为 $0$ 到 $c-1$；还有 $n$ 个箱子，编号为 $1$ 到 $n$，最开始每个箱子的颜色为 $1$。

小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择 $[L,R]$ 这个区间里的一些箱子（不选看做选 $0$ 个），为之涂上随机一种颜色。若一个颜色为 $a$ 的箱子被涂上 $b$ 色，那么这个箱子的颜色会变成 $(a\times b)\bmod c$。请问在 $k$ 次涂色后，所有箱子颜色的编号和期望为多少？

输入格式

输入文件名为 elephant.in。

第一行为 $T$，表示有 $T$ 组测试数据。

对于每组数据，第一行为三个整数 $n,c,k$。

接下来 $k$ 行，每行两个整数 $L_i,R_i$，表示第 $i$ 个操作的 $L$ 和 $R$。

输出格式

输出文件名为 elephant.out。

对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留 $9$ 位小数。

输入样例

3
3 2 2
2 2
1 3
1 3 1
1 1
5 2 2
3 4
2 4

输出样例

2.062500000
1.000000000
3.875000000

数据范围

对于 $40\%$ 的数据满足：$1\le T\le5$，$1\le n,k\le15$，$2\le c\le20$；

对于 $100\%$ 的数据满足：$1\le T\le10$，$1\le n,k\le50$，$2\le c\le100$，$1\le L_i\le R_i\le n$。