「LAOI-15」天天爱阅读
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小 P 正在内卷新算法！他在网上找到了 n 篇文章，将它们依次标号为 1,2,\dots,n。其中，第 i 篇文章的价值为 a_i，读这篇文章需要耗费 b_i 的体力值。已知所有文章的价值互不相同。
\hspace{15pt}小 P 的学习时间有限，所以他最多只会读 k 篇文章。更具体地，小 P 有一个编号区间 [l,r](1\leq l\leq r\leq n)，他会从编号落在这个区间内的文章中，选择最多 k 篇文章阅读，使得他所阅读的文章的价值和最大（换句话说，他会从该区间内选择价值最大的 \min(k, r-l+1) 篇文章）。
\hspace{15pt}现在小 P 想知道，对于所有可能的编号区间，他将耗费的体力值的总和。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

输入描述:

\hspace{15pt}第一行输入两个整数 n,k \left(1\leq n\leq 10^5;\ 1\leq k\leq\min(n,50)\right)，表示文章的数量、小 P 最多阅读的文章数量。
\hspace{15pt}第二行输入 n 个互不相同的整数 a_1,a_2,\dots,a_n \left(1\leq a_i\leq 10^9\right)，表示每篇文章的价值。
\hspace{15pt}第三行输入 n 个整数 b_1,b_2,\dots,b_n \left(1\leq b_i\leq 10^9\right)，表示每篇文章耗费的体力值。

输出描述:

\hspace{15pt}输出一个整数，表示小 P 耗费的体力值的总和，对 10^9+7 取模。
示例1

输入

复制 
2 1
1 14
51 4

输出

复制 
59

说明

\hspace{15pt}在这个样例中，由于小 P 只会读 1 篇文章，所以他一定会阅读区间内价值最大的一篇文章：
\hspace{23pt}\bullet\,当编号区间为 [1,1] 时，小 P 会读第 1 篇文章，耗费的体力值为 51；
\hspace{23pt}\bullet\,当编号区间为 [2,2] 时，小 P 会读第 2 篇文章，耗费的体力值为 4；
\hspace{23pt}\bullet\,当编号区间为 [1,2] 时，小 P 会读第 2 篇文章，耗费的体力值为 4。
\hspace{15pt}综上，答案即为 51+4+4=59。
示例2

输入

复制 
10 4
84 853 264 368 372 263 78 499 260 672
46 111 27 633 739 89 554 678 133 191

输出

复制 
67612