采蘑菇的小西佬找到了一张上古年间的藏宝图,上面画着m座连绵不断的山,他决定去地图上记载的地点探险,可当他到达时,他发现当地其实有n座山,并且由于年代久远有些山也改变了形状,他不能准确的找到地图上藏宝的地点,于是他决定从一些连续的山中随意选择一座山作为地图上的第一个点,当他选定了起点以后,若当前的山与地图上记载山的高度相同他就会继续前往下一座山,否则就停下来,直到他到达地图上的最后一座山位置.我们假设如果他经过了大于k座山他就能找到宝藏(如果第一座山高度就不相同,视为经过0座山),现在的问题就是他有多大的可能性找到宝藏.
k=(ans*10086+666)%x;
ans代表上一次询问的答案,x=min(m,r-l+1);
第一行输入三个数n,m,k(1<=nmk<=1e5);
第二行输入n个数代表n座山的高度(1<=a[i]<=1e9)
第二行输入m个数代表m座山的高度(1<=b[i]<=1e9)
第四行输入一个数q;(1<=q<=1e5)
接下来每行输入两个整数l,r;(1<=l<=r<=n)
对于每个询问请输出对应的概率,以逆元的形式输出(mod=1e9+7);