题目描述
采蘑菇的小西佬找到了一张上古年间的藏宝图，上面画着ｍ座连绵不断的山，他决定去地图上记载的地点探险，可当他到达时，他发现当地其实有ｎ座山，并且由于年代久远有些山也改变了形状，他不能准确的找到地图上藏宝的地点，于是他决定从一些连续的山中随意选择一座山作为地图上的第一个点，当他选定了起点以后，若当前的山与地图上记载山的高度相同他就会继续前往下一座山，否则就停下来，直到他到达地图上的最后一座山位置。我们假设如果他经过了大于ｋ座山他就能找到宝藏（如果第一座山高度就不相同，视为经过０座山），现在的问题就是他有多大的可能性找到宝藏。
题目共有ｑ次询问，每次询问有两个整数ｌ，ｒ代表采蘑菇的小西佬选择的区间，并且会给出第一次询问的ｋ，之后的每个询问的ｋ按照下面的式子算出
ｋ＝（ａｎｓ＊１００８６＋６６６）％ｘ；
ａｎｓ代表上一次询问的答案，ｘ＝ｍｉｎ（ｍ，ｒ－ｌ＋１）；
输入
第一行输入三个数ｎ，ｍ，ｋ(1<=n,m,k<=1e5);
第二行输入ｎ个数代表ｎ座山的高度(1<=a[i]<=1e9)
第二行输入ｍ个数代表ｍ座山的高度(1<=b[i]<=1e9)
第四行输入一个数ｑ;(1<=q<=1e5)
接下来每行输入两个整数ｌ，ｒ；(1<=l<=r<=n)
输出
对于每个询问请输出对应的概率，以逆元的形式输出（ｍｏｄ＝１ｅ９＋７）；
样例输入
7 5 1
1 3 2 1 3 5 4
1 3 5 4 6
2
3 5
2 4
样例输出
333333336
333333336
提示
对于第一个询问，ｋ＝１，以３为起点能走过０座山，以４为起点能走过４座山，以５为起点能走过０座山，所以大于ｋ的有１个
对于第二个询问，ｋ＝（333333336*10086+666）%min(5,4-2+1)=0，以2为起点能走过０座山，以3为起点能走过0座山，以4为起点能走过４座山，所以大于ｋ的有１个
浙江理工大学月赛2019年5月
来源/分类
浙江理工大学月赛