题目描述

小九是个天赋异禀的孩子。尤其在信息学方面，学习不满一年，他的成绩便已远远超出了学校里久居机房的高年级前辈们。天赋固然重要，但小九知道，要早日实现他的真正目标，努力必不可少。为此，小九制定了一项训练计划。 他的训练计划共包括 $N$个习题，编号 $1 \sim N$ ，第 $i$ 个习题能为小九带来收获值 $g_i$ 。迫不及待的小九，今天就开始执行自己的训练计划了。他会以每天一题的速度，按顺序做题。

当然，小九并不想让自己的训练过程过于枯燥，因此对于任意连续编号的习题而言，小九至多只会选择其中的 $K$ 题。

现在，小九想提前知道，当他完成此项训练计划时，他所选择的习题的收获值的乘积，最大会是多少？

输入格式

第一行，两个整数 $N、K$，意义如上。

第二行，$N$ 个用空格分隔的整数，其中第 $i$ 个整数表示相应编号习题的收获值 $g_i$

输出格式

一个整数，表示所选习题的最大收获值乘积。输出计算结果对 $10^9 + 7$ 取模后的数值即可。

输入样例1

4 2
2 5 3 5

输出样例1

50

数据范围

$1 \leq N \leq 10^6, 1 \leq g_i \leq 9$