2018 博士生面试机考

E. Walking through hyperspace

单点时限: 1.5 sec

内存限制: 1024 MB

我们继续来学小学数学。小学生都会做这样一个题:给一个 的网格,一开始在 ,每次只能向上向右走一步,问有多少种不同的方案到达

相信这道题一定难不倒作为大学生的你。但作为善良的出题人,你若解决了这个问题,你就能获得 30 分。

对于初中生而言,我们就可以解决三维的情况,有一个 的网格,一开始在 ,每次只能向前向上向右走一步,问有多少种方案到达

相信这道题同样难不倒作为大学生的你。但作为善良的出题人,你若解决了这个问题,你能获得 60 分。

我们不妨将这个问题一般化,在一个超空间中,有一个零点,和一个给定点 。一开始有 ,每次操作可以选择 ,然后对 的某一维加 。问有多少种不同的方案使得 最终变成

输入格式

第一行一个整数

第二行 个整数,用空格隔开,分别为

部分分约定:

  • :
  • : 不全为
  • :

输出格式

输出一个整数表示方案数。由于答案可能很大,对 取模。

样例

Input
2
0 5
Output
1
Input
2
1 1
Output
2
Input
2
4 3
Output
35
Input
3
1 1 1
Output
6