【日常小测】最长路径

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

首先我们要熟悉竞赛图的两个结论:

  1. 任意一个竞赛图一定存在哈密尔顿路径
  2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和

设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$

于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

Code

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

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	n = read(); MOD = read();
	pw[0] = 1;
	for (int i = 1; i < n * n; i++) {
		pw[i] = (pw[i - 1] << 1) % MOD;
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	f[0] = g[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = g[i] = pw[i * (i - 1) >> 1];
		for (int j = 1; j < i; j++) {
			g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
		}
	}
	for (int x = 1; x <= n; x++) {
		int ans = 0;
		for (int i = 1; i <= x; i++) {
			ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
		}
		printf("%d\n", ans > 0? ans: ans + MOD);
	}
	return 0;
}

【TopCoder SRM714】ParenthesisRemoval

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14595&rd=16883

解题报告

不难发现,这就是统计括号匹配的方案数
不会的同学可以先去切BZOJ 3622

Code

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

const int N = 3000;
const int MOD = 1000000007;

int n,ans;
char s[N]; 

class ParenthesisRemoval {
    public:
    	int countWays(string ss) {
			n = ss.size();
    		for (int i=0;i<ss.size();i++) {
				s[i] = ss[i];
			}
			ans = 1;
			for (int i=0,pfx=0;i<n;i++) {
				if (s[i] == '(') {
					++pfx;
				} else {
					ans = (LL)ans * (pfx--) % MOD;
				}
			}
    	    return ans;
   		}
   	private:
};

【BZOJ 4714】旋转排列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4714
神犇题解:http://www.cnblogs.com/clrs97/p/6358603.html

题目大意

定义集合$A=\{1,2,\cdots,n\}$
对于$A$的任意一个排列$P$,其对于自然数$k$合法当且仅当:

  1. 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
  2. 存在一个长度为$k$的序列$B$,使得$P_{B_i}=B_{i+1}$且$P_{B_k} = B_1$

定义$k=x$时$A$的合法排列数为$ans_x$,询问$\sum\limits_{i=1}^{n}{ans_i}$
由于答案可能很大,输出答案对$10^9 + 7$取模得到的结果

解题报告

我们发现,要求合法的第二个限制实际就是要求置换存在一个等于$k$的循环
于是我们对于每一个$k$,我们容斥一发,根据调和级数,这个复杂度是:$O(n \log n)$的

至于容斥的具体细节,假设我们当前钦定有$t$个长度为$k$的循环
设把$tk$个数分成$k$个循环的方案数为$g_{k,t}$
设$i$个数的错排的方案数为$d_i$
设$i$个数的环排列的方案数为$q_i$
那么这一部分的总方案数为:$g_{k,t} \cdot d_{n-kt} \cdot {{n} \choose {kt}}$

至于$q_i$怎么算?$q_i = (i-1)!$
至于$d_i$怎么算?我们可以$O(n)$预处理
至于$g_{k,t}$怎么算?我们考虑$1$所在的那个循环有哪些数,可以得到:$g_{k,t}=g_{k,t-1} \cdot d_k \cdot {{tk-1} \choose {k-1}}$

Code

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

const int N = 500009;
const int MOD = 1000000007;

int n,ans,fac[N],rev[N],q[N];

inline int C(int a, int b) {
	if (a > b || a < 0) return 0;
	else return ((LL)fac[b] * rev[a] % MOD) * rev[b-a] % MOD;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t&1) ret=(LL)ret*w%MOD;
	return ret;
}

int main() {
	fac[0] = fac[1] = q[2] = q[0] = 1; 
	for (int i=2;i<N;i++) fac[i] = (LL)fac[i-1] * i % MOD;
	rev[N-1] = Pow(fac[N-1], MOD - 2);
	for (int i=N-2;~i;i--) rev[i] = rev[i+1] * (i + 1ll) % MOD; 
	for (int i=3;i<N;i++) q[i] = (i - 1ll) * (q[i-1] + q[i-2]) % MOD;
	cin>>n;
	for (int k=2,g;g=1,k<=n;k++) {
		for (int t=1;t*k<=n;t++) {
			g = ((LL)g * C(k-1, t*k-1) % MOD) * fac[k-1] % MOD;
			ans = (ans + ((t&1)?1:-1) * ((LL)g * C(k*t, n) % MOD) * q[n - k*t]) % MOD;
		} 
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4710】[JSOI2011] 分特产

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4710
神犇题解:http://www.cnblogs.com/candy99/p/6616858.html

解题报告

先不考虑每个人至少一个的限制条件
那么我们可以将每一类物品分别考虑,用一个插板法就可以解决问题

现在考虑每一个人至少一个的限制
我们可以大力容斥一波!

于是总的时间复杂度就是:$O(nm)$

Code

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

const int N = 2009;
const int MOD = 1000000007;

int n,m,ans,a[N],C[N][N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int cal(int x) {
	int ret = C[x][n];
	for (int i=1;i<=m;i++) {
		ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
	}
	return ret;
}

int main() {
	n = read(); m = read(); 
	C[0][0] = 1;
	for (int i=1;i<N;i++) {
		C[0][i] = 1;
		for (int j=1;j<N;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	}
	for (int i=1;i<=m;i++) a[i] = read();
	for (int i=0;i<n;i++) {
		if (i&1) ans = (ans - cal(i)) % MOD;
		else ans = (ans + cal(i)) % MOD;
	} 
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4735】你的生命已如风中残烛

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4735
神犇题解:http://blog.csdn.net/neither_nor/article/details/64919143

吐槽

我只会$O(mn2^n)$的暴力$DP$
然而正解长成这样,为什么$n$给这么小?
给人一种这题有妙妙的做法的错觉……

解题报告

我们把正常的牌看成$-1$的话,那么实际上就是要让每一个地方的前缀和$\ge 1$

现在考虑在末尾加上一个$-1$,那么是不是就是处末尾以外的地方$\ge 1$,而末尾的前缀和为$0$?
现在考虑把这$m+1$个元素拿出来做一个环排列
仔细观察可以发现:一种环排列能且仅能对应一种合法摆放
于是我们求出环排列的个数就可以了,最后再去一下多加的那个$-1$的影响
最终答案:$\frac{m!}{m-n+1}$

Code

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

const int MOD = 998244353;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	int n = read(), m = 0, ans = 1;
	for (int i=1;i<=n;i++) m += read();
	for (int i=2;i<=m;i++) ans = ((LL)ans * ((i!=m-n+1)?i :1)) % MOD;
	cout<<ans;
	return 0;
}

【HDU 4349】Xiao Ming’s Hope

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4349
神犇题解:http://blog.csdn.net/u013486414/article/details/48130553

题目大意

求${n \choose i},i \in [1,n]$中有多少个奇数
其中$n \le 10^{18}$

解题报告

原题相当于求${n \choose i} \% 2$有多少个为$1$
考虑使用$Lucas$定理,将模数设为$2$
此时相当于把$n,i$都转成了二进制下,然后单独考虑每一位
因为${1 \choose 1} = {1 \choose 0} = {0 \choose 0} = 1,{0 \choose 1} = 0$
所以当$n$的那个二进制位为$1$的时候,$i$那一位可以为$0/1$,但当$n$那一位为$0$时,$i$只能为$0$
所以最终方案数为$2^{\sum\limits_{i=0}^{63}{(n>>i) \& 1}}$

Code

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

int main() {
	for (LL n,ans;~scanf("%I64d",&n);){
		ans = pow(2, __builtin_popcountll(n)) + 0.5;
		cout<<ans<<endl;
	}
	return 0;
}

【BZOJ 3925】[ZJOI2015] 地震后的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3925
神犇题解Ⅰ:http://blog.csdn.net/skywalkert/article/details/47792065
神犇题解Ⅱ:http://www.cnblogs.com/yousiki/p/6437155.html

解题报告

题目上说:

对于$n$个$[0,1]$之间的随机变量$x_1,x_2,\cdots ,x_n$,第$k$小的那个的期望值是$\frac{k}{n+1}$

即加入$k$条边后恰好有生成树的情况的最大边的期望权值为$\frac{k}{n+1}$
设$g_k$为加入$k$条边后恰好使所有点连通的方案数
于是原题的答案为$\frac{1}{m+1}\sum\limits_{i=1}^{m}{\frac{i \cdot g_i}{m \choose i}}$

设$f_k$为加入$k$条边后原图不连通的方案数
我们可以交换一下求和顺序可使答案变为:$\frac{1}{m+1}\sum\limits_{i=0}^{m}{\frac{f_i}{m \choose i}}$
于是问题变为求$f_k$与$g_k$

我们首先可以发现,$f_k$加$g_k$一定等于所有的方案
那么设点集$S$的诱导子图中的边数为$cnt_{S}$,仅对于点集$S$有效的$f_k,g_k$为$f_{S,k},g_{S,k}$
则有:$f_{S,k}+g_{S,k}={cnt_S \choose k}$,于是只需要求出$g_{S,k},f_{S,k}$中的任意一个

类比带标号的连通图计数,我们可以列出递推式:$f_{S,i+j} = \sum\limits_{T \subset S}{g_{T,i} {cnt_{S-T} \choose j}}$
又$g_{S,k}={cnt_S \choose k} – f_{S,k}$,所以这个递推式可以直接递推
于是这题就做完啦!时间复杂度:$O(m 4^n)$
又因为上述$T \subset S$所以我们直接枚举子集,复杂度优化到$O(m 3^n)$

【BZOJ 3028】食物

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解:http://blog.csdn.net/regina8023/article/details/44995939

解题报告

这题看上去一眼不可做啊!第一反应:还要写高精?
但想一想似乎物品非常妙妙:

我们强行将其分为四组:{汉堡,可乐} {蜜桃多,土豆片炒肉} {包子,鸡块} {鸡腿,面包}
我们发现每一组都能凑出每一个自然数,且方案唯一
于是问题变为将$n$个球分为$4$组,每组可以为空的方案数

这是插板法的经典问题,于是搞一个组合数就可以了
什么组合数太大?
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$,所以我们取个模就可以了

当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ

Code

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

const int MOD = 10007;
const int REV = 1668;

int main() {
	int n=0; char pat[600]; cin>>pat+1;
	for (int i=1;i<=strlen(pat+1);i++)
		n = (n * 10 + pat[i] - '0') % MOD;
	cout<<n*(n+1ll)*(n+2)*REV%MOD;
	return 0;
}

【日常小测】计数

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/03/20170301145817_34363.png
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/03/20170301150237_94661.png

一句话题意

给$n_1$个$A$,$n_2$个$B$,$n_3$个$C$,$n_4$个$D$
问有多少种排列方式,使得相邻两项全部不同
$n_1,n_2,n_3,n_4 \le 10^3$

吐槽

因为做过魔法的碰撞
所以这题卡在$O(n^3)$的复杂度上卡了三个半小时 QwQ
最后暴力还$MLE$了 QwQ

解题报告

假设我们知道了将$A,B$分成$i$段、每一段中相邻两项不同的方案数为$f_i$
知道了将$C,D$分成$i$段、每一段中相邻两项不同的方案数为$g_i$
那么答案显然为$\sum\limits_{i=1}^{n_1+n_2}{f_i \cdot (g_{i-1}+2g_i+g_{i+1})}$
至于中间那一项为什么要乘以2? 因为多出来那一段我们既可以放段首,也可以放段尾

现在唯一的问题就是如何求出$f_i,g_i$了
考虑仅由$A,B$组成的字符串,一定为以下四种情况之一

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

假如我们枚举第一种情况出现了$i$次
那么第二种情况的出现次数$j=i-(a-b)$
那剩下的$k$次,就是第三种和第四种了,不难发现我们乘上$2^k$之后他们就可以视为等价
于是我们先在第一种情况的位置上插入$A$,第二种情况插入$B$,第三、四种情况插入$AB(BA)$
之后我们相当于把剩下的$A,B$两两配对,然后分成$x$组,允许空集
那么这就是插板法的板题了

于是我们就用上述算法处理出$f_i,g_i$即可
时间复杂度:$O(n^2)$

Code

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

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int solve(int a, int b, int c) {
	if (a < b) swap(a, b);
	if (!a && b) return b == c;
	int ret = 0;
	for (int i=a-b,j,k;i<=c;++i) {
		j = i - a + b; k = c - i - j;
		if (j >= 0 && k >= 0 && a >= i + k ) {
			(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
		}
	}
	return ret;
}

int main() {
	PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
	C[0][0] = 1; for (int i=1;i<N;i++) {
		C[0][i] = 1; for (int j=1;j<=i;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	} 
	int a=read(),b=read(),c=read(),d=read();
	if (a + b == 0) f[1] = 1;
	else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
	if (c + d == 0) g[1] = 1;
	else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
	for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
	printf("%d\n",vout);
	return 0;
}

【Codeforces 653G】Move by Prime

相关链接

题目传送门:http://codeforces.com/problemset/problem/653/G
官方题解:http://codeforces.com/blog/entry/43886
数学推导参考:http://codeforces.com/blog/entry/43886?#comment-285657
中文题面:http://www.cnblogs.com/AOQNRMGYXLMV/p/5441441.html
生成函数的做法:http://www.cnblogs.com/AOQNRMGYXLMV/p/5441441.html

解题报告

不难发现质因数之间相互独立
于是我们就可以将每一个质因数单独考虑
这样问题转化为:

给定一个序列 {$ { {a_i}}$} ,每一次操作可以选一个数加一或者减一
问:将序列中所有数变为相同至少需要多少次操作

这个经典的问题,我们都知道全部变到中位数是较优的策略
但如何考虑每一个子序列?似乎没有比较优雅的方法…

于是我们换一个角度考虑:

设序列排序后为 {\({ {b_i}}\)}, 中位数为 $ {b_{mid}}$
那么这个序列的花费为 $ \sum\limits_{i = 1}^{mid – 1} {({b_{mid}} – {b_i})} + \sum\limits_{i = mid + 1}^n {({b_i} – {b_{mid}})}$

打开∑之后发现 $ {b_{mid}}$ 全部抵消掉了!
于是我们统计一个数有有多少次是加上或是减去就好啦!

考虑当前处理 $ {b_k}$ 这样的话,枚举有i个数比他小
那么有 $ i+1 \sim n-k$ 个数比他大的情况全部是减去
有 $ 0 \sim i-1$ 个数比他大的情况全部是加上
写出来就是 $ \sum\limits_{i = 0}^{{\rm{k – 1}}} {(\sum\limits_{j = {\rm{0}}}^{i – 1} {C_{n – k}^j} – \sum\limits_{j = i + 1}^{n – k} {C_{n – k}^j} )} \cdot {b_k}$

但这样计算的话,复杂度不对,于是再化简一下:

考虑选法1:左边选 $ l$ 个,右边选 $ r$ 个,$ r-l=x$
这样的话,我们总共选了 $ r+l$ 个数
考虑将右边选的数反选(方案间仍然一一对应),此时我们选择了 $ n-k-x$ 个数

再考虑选法二:我们任选 $ n-k-x$ 个数
因为 $ r-l=x$, 所以一定可以构造出唯一一组 $ (l,r)$ 使得 $ l+r=n-k-x$

于是我们就证明了上述两种选法存在一种一一对应的映射
换一句话来说,我们可以直接统计第二种选法的方案数 $ C_{n – 1}^{n – k – x}$ 即可

这样的话,答案就成了 $ (\sum\limits_{i = – 1}^{ – (k – 1)} {C_{n – 1}^{n – k – i} – \sum\limits_{i = 1}^{n – k} {C_{n – 1}^{n – k – i}} ) \cdot {b_k} = } (\sum\limits_{i = n – k + 1}^{n – 1} {C_{n – 1}^i – \sum\limits_{i = 0}^{n – k – 1} {C_{n – 1}^i} ) \cdot {b_k}}$
这样的话,我们处理一下组合数的前缀和就可以 $ O(n)$ 处理完每一个质因数了
又因为 $ {b_k}$ 的值域很小,于是再预处理一下组合数的前缀和的前缀和
就可以得到 $ O(nlog(n))$ 的复杂度辣!

当然上面数学推导那一块还可以用生成函数来推导
然而我不会 QwQ

Code

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

const int N = 300000+9;
const int L = 22;
const int MOD = 1000000007;

int n,tot,vout,pri[N],vis[N],sur[N],cnt[N][L];
int POW[N],REV[N],sum[N],pre1[N],pre2[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int C(int a, int b) {
	if (a > b || a < 0 || b < 0) return 0;
	else return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD;
}

inline int pre_sum(int l, int r) {
	if (l > r) return 0;
	return (sum[r] - (l?sum[l-1]:0)) % MOD;
}

inline int Pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline void prework() {
	n = read(); sur[1] = 1;
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, sur[i] = tot;
		for (int j=1;j<=tot&&pri[j]*i<N;j++) {
			vis[i*pri[j]] = 1;
			sur[i*pri[j]] = j;
			if (i % pri[j] == 0) break;
		}
	}
	for (int i=1;i<=tot;i++)
		cnt[i][0] = n;
	
	POW[0] = REV[0] = 1;
	for (int i=1;i<N;i++)
		POW[i] = (LL)POW[i-1] * i % MOD;
	REV[N-1] = Pow(POW[N-1], MOD-2);
	for (int i=N-2;i;i--)
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
	sum[0] = 1;
	for (int i=1;i<N;i++) 
		sum[i] = (sum[i-1] + C(i, n-1)) % MOD;
	for (int i=1;i<=n;i++)
		pre1[i] = (pre_sum(n-i+1, n-1) - pre_sum(0, n-i-1)) % MOD;
	for (int i=1;i<=n;i++)
		pre2[i] = (pre2[i-1] + pre1[i]) % MOD;
}

int main() {
	prework();
	for (int i=1,w;i<=n;i++) {
		w = read();
		for (int j=sur[w],tmp;w>1;j=sur[w]) {
			for (tmp=0;w%pri[j]==0;tmp++,w/=pri[j]);
			cnt[j][tmp]++;
			cnt[j][0]--;
		}
	}
	for (int i=1;i<=tot;i++) {
		if (cnt[i][0] < n) {
			for (int j=0,l=0,r=0;j<L;j++) {
				if (cnt[i][j]) {
					r += cnt[i][j];
					(vout += (LL)(pre2[r] - pre2[l]) * j % MOD) %= MOD;
					l = r;
				}
			}
		}
	}
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}