U281889 数列切分

题目来源：[PAT (Top Level) Practice](https://pintia.cn/problem-sets/994805148990160896/exam/problems/1478636403210989568)

给定一个长度为 $n$ 的整数数列，通过恰好 $(m - 1)$ 次切分得到 $m~(\le n)$ 个子数列 定义数列切分的**分值**为：各子数列元素和的乘积 你的任务是计算所有可能的切分方法得到的分值之积

第一行输入两个正整数 $n, m~(1 \le m \le n \le 10^3)$ 第二行包含 $n$ 个 $\le 10^9$ 的正整数

输出所有可能的切分方法得到的分值之积 由于答案数值可能很大，你只需要输出其对 $10^9 + 7$ 取模后的结果

### 样例说明 对于样例中的数列，可能的切分方法有： 1. $(5)~(1~2~3~4)$：分值为 $5 \times (1 + 2 + 3 + 4) = 50$ 1. $(5~1)~(2~3~4)$：分值为 $(5 + 1) \times (2 + 3 + 4) = 54$ 1. $(5~1~2)~(3~4)$：分值为 $(5 + 1 + 2) \times (3 + 4) = 56$ 1. $(5~1~2~3)~(4)$：分值为 $(5 + 1 + 2 + 3) \times 4 = 44$ 最终结果为 $50 \times 54 \times 56 \times 44 = 6652800$