#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair P; const int MAX_N=1<<20; const ll MOD=1e9+7; ll sum[2*MAX_N-1], parta[2*MAX_N-1], partb[2*MAX_N-1], partf[2*MAX_N-1]; int m; ll fib1[MAX_N], fib[MAX_N]; void init(int n){ m=1; while(m0 || partf[k]>0){ ll s=fib[r-1]; if(l>0) s+=(MOD-fib[l-1]); sum[k]=(sum[k]*parta[k]+partb[k]*((ll)(r-l))+partf[k]*s)%MOD; if(k