Young diagram（杨图）是一种满足以下规则的行与列的方格排列：

• 每一行和每一列的方格都是连续的，
• 所有行的左边界对齐，
• 每一行的长度都不超过其上方的那一行。

以下是一些 Young diagram 的示例：

对于给定的数字 $N$，半标准 Young tableau（半标准杨表）是指一个填充了数字的 Young diagram，且满足以下规则：

• 每个方格包含一个 $1$ 到 $N$ 之间的整数（包含 $1$ 和 $N$），
• 每个整数大于或等于其左侧方格中的整数，
• 每个整数严格大于其上方方格中的整数。

以下是对于 $N = 3$，基于某个特定 Young diagram 的所有半标准 Young tableau 列表：

你的任务是计算对于给定的 Young diagram 和给定的 $N$，有多少种可能的半标准 Young tableau。

输入格式

每个测试用例包含两行。第一行指定 Young diagram。该行以数字 $k$ 开头（满足 $1 \le k \le 7$），表示行数，随后是 $k$ 个正整数 $l_1, l_2, \dots, l_k$。这些整数指定了 Young diagram 每一行的方格数，且满足 $7 \ge l_1 \ge l_2 \ge \dots \ge l_k \ge 1$。第二行包含整数 $N$，满足 $k \le N \le 7$。

输出格式

对于每个测试用例，输出一行，包含基于给定的 Young diagram 和给定的 $N$ 的半标准 Young tableau 的数量。

样例

输入 1

1 1
1

输出 1

1

输入 2

1 1
2

输出 2

2

输入 3

2 2 1
4

输出 3

20

输入 4

4 3 2 1 1
4

输出 4

20