[CC-CMPVIRS]Computer Virus

题目大意：

有一张纸带，从左到右被分成了\(n(n\le10^7)\)个格子，在刚开始，第\(i\)个格子上写着数字\(i\)。这张纸带被分成了从左到右的连续的\(m(m\le10^3)\)段，编号较小的段在编号较大的段的左边，且每一个格子都被分给了其中的一段。第\(i\)段有\(d_i\)个格子。

另外，编号较大的段的格子数不小于编号较小的段，即\(d_i\le d_{i+1}\)。

刚开始所有格子都是白色的，现在重复以下操作，直到所有格子都被染成黑色:

1. 将每段的最后一个格子染成黑色。
2. 将每一个白色格子上写的数改成它和它左边的白色格子上的数之和,这个过程所有的白色格子是同时完成的。

求所有格子都被染成黑色后，格子上的数字和，模\(10^9+7\)。

思路：

进行一些合理猜测就可以得到结论（见代码）。

证明见官方题解。

源代码：

#include<cstdio>

#include<cctype>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int M=1001,mod=1e9+7;

inline int power(int a,int k) {

	int ret=1;

	for(;k;k>>=1) {

		if(k&1) ret=(int64)ret*a%mod;

		a=(int64)a*a%mod;

	}

	return ret;

}

int d[M];

int main() {

	const int n=getint(),m=getint();

	int ans=mod-m;

	for(register int i=1;i<=m;i++) {

		int tmp=1;

		d[i]=getint();

		for(register int j=0;j<i;j++) {

			tmp=(int64)tmp*power(i-j+1,d[j+1]-d[j])%mod;

		}

		(ans+=tmp)%=mod;

	}

	printf("%d\n",ans);

	return 0;

}