题目描述
虽然不知道为什么，但是你一直想用一种神奇的方式完成一幅画作。
你把n张画纸铺成一排，并将它们从1到n编号。你一共有c种颜色可用，这些颜色可以用0到c-1来编号。初始时，所有画纸的颜色都为1。你一共想进行k次作画，第i次作画时，你会等概率随机地选闭区间[Li,Ri]内的画纸的一个子集（可以为空），再随机挑一种颜色bi，并把挑出来的画纸都涂上该颜色。原有颜色a的画纸在涂上颜色b后，颜色会变成(a*b) mod c，这是这个世界的规律。
因为你将颜色用数字来命名了，因此你可以求出在k次作画结束后，每张画纸上的颜色对应的数字相加之和的期望。现在请你编程求一下这个值。

输入格式
第一行包含3个正整数n, c, k，意义如题所述。
接下来k行，每行包含两个数Li, Ri，表示你每次操作会从哪个区间内随机地选画纸。

输出格式
一行，一个小数，表示答案，四舍五入精确到小数点后3位。

样例输入1

2 3 1
1 2

样例输出1

2.000

样例解释
一共有4种选择子集的可能，每种的概率都是。
选空集：画纸不会发生改变，颜色和是1+1=2；
选{1}：画纸2不会发生改变。选颜色有3种可能，使得画纸1最终分别变成颜色0、1、2，概率都是1/3，颜色和的期望是1/3*((0+1)+(1+1)+(2+1))=2;
选{2}：与选1对称，颜色和的期望也是2；
选{1,2}：选颜色有3种可能，使得两张画纸最终都变成颜色0、1、2，概率都是，颜色和的期望是1/4*(2+2+2+2)=2；
综上，4种选择子集的方案的颜色和的期望为2。

样例输入2

3 3 3
1 2
2 3
1 3

样例输出2

2.639

数据范围
对100%数据，n、c、k<=100
对所有数据，1≤Li≤Ri ≤n。