如果你用的是容斥做法，

注意前缀和优化时要 +mod %mod

即

dp[i][0]=(val(p,0,dp)+(val(i-1,1,q)-val(p-1,1,q))*a[i]%mod)%mod;
dp[i][1]=(val(p,1,dp)+(val(i-1,0,q)-val(p-1,0,q))*a[i]%mod)%mod;

->

dp[i][0]=(val(p,0,dp)+(val(i-1,1,q)-val(p-1,1,q)+mod)%mod*a[i]%mod)%mod;
dp[i][1]=(val(p,1,dp)+(val(i-1,0,q)-val(p-1,0,q)+mod)%mod*a[i]%mod)%mod;