题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6656
题目大意：
t个样例
有n+1个关卡， m次询问。

对于一个关卡，
r s x a
表示有r/s通过关卡， 每次尝试花费a元， 失败回到x关。

每次询问L R询问从L关卡到R关卡，期望花费多少钱？
dp[i]表示从1 - i关的期望的花费。

Sample Input
1
3 2
1 1 1 2
1 2 1 3
1 3 3 4
1 4
3 4

Sample Output22
12

d p [ i ] = d p [ i − 1 ] + p i ∗ w i + ( 1 − p i ) ∗ ( w i + d p [ i ] − d p [ x ] ) dp[i] = dp[i-1] + p_i*w_i + (1-p_i)*(w_i+dp[i]-dp[x]) dp[i]=dp[i−1]+pi​∗wi​+(1−pi​)∗(wi​+dp[i]−dp[x])
p：概率 w：花费 x:回到的关卡

化简： d p [ i ] = ( d p [ i − 1 ] + w i − d p [ x ] ) / p i dp[i]=(dp[i-1]+w_i-dp[x])/pi dp[i]=(dp[i−1]+wi​−dp[x])/pi

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int mod = 1e9+7;

LL poww(LL a,LL b){
    LL ans=1,base=a;
    while(b!=0){
        if(b&1!=0)
        {
            ans*=base;
            ans%=mod;
        }
	base=base*base%mod;
        b>>=1;
    }
    return ans%mod;
}

LL dp[500005];
struct node
{
    LL p, q, x, w;

}a[500005];

LL dfs(LL n)
{
    if(dp[n]!=0||n==1)
    {
        return dp[n];
    }

    LL s=dfs(n-1)+mod+a[n].w-dfs(a[n].x);
    s%=mod;

    s*=a[n].q;
    s%=mod;

    s*=poww(a[n].p, mod-2);
    s%=mod;

    s=s+dfs(a[n].x);
    s%=mod;

    return dp[n]=(s+mod)%mod;

}

int main()
{
    LL t;
    scanf("%lld", &t);
    while(t--)
    {
        memset(dp, 0, sizeof(dp));
        LL n, m;
        scanf("%lld%lld", &n, &m);
        for(LL i=2;i<=n+1;i++)
        {
            scanf("%lld%lld%lld%lld", &a[i].p, &a[i].q, &a[i].x, &a[i].w);
        }

        dfs(n+1);
        while(m--)
        {
            LL L, R;
            scanf("%lld%lld", &L,&R);
            printf("%lld\n", (dp[R]-dp[L]+mod)%mod);
        }
    }

    return 0;
}