时间限制： 1.0 秒

空间限制： 256 MB

题目描述

给定一个长度为 $n$ 的整数数列，通过恰好 $(m - 1)$ 次切分得到 $m~(\le n)$ 个子数列。

定义数列切分的分值为：各子数列元素和的乘积。

你的任务是计算所有可能的切分方法得到的分值之积。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n, m~(1 \le m \le n \le 10^3)$。

第二行包含 $n$ 个 $\le 10^9$ 的正整数。

输出格式

输出到标准输出。

输出所有可能的切分方法得到的分值之积。

由于答案数值可能很大，你只需要输出其对 $10^9 + 7$ 取模后的结果。

5 2
5 1 2 3 4

6652800

样例 1 解释

对于样例中的数列，可能的切分方法有：

1. $(5)~(1~2~3~4)$：分值为 $5 \times (1 + 2 + 3 + 4) = 50$；
2. $(5~1)~(2~3~4)$：分值为 $(5 + 1) \times (2 + 3 + 4) = 54$；
3. $(5~1~2)~(3~4)$：分值为 $(5 + 1 + 2) \times (3 + 4) = 56$；
4. $(5~1~2~3)~(4)$：分值为 $(5 + 1 + 2 + 3) \times 4 = 44$；

最终结果为 $50 \times 54 \times 56 \times 44 = 6652800$。

来源

PAT 顶级 1029