#1698. 小 P 爱学习

    ID: 1698 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1048来源:qoj.ac数据:公开样例动态规划组合数学

小 P 爱学习

小 P 爱学习

题目描述

标题: 小 P 爱学习 - Problem - QOJ.ac

#5097. 小 P 爱学习

Statistics

The problem was used in the following contests:

小 P 得到了 nm 本有序的书,第 i 本书有一个权值 ai,下标从 1 开始。

作为一个卷怪,他想把这些数分成若干无序的组以便学习,使得分到每组的书的数量都是 m 的倍数。

小 P 认为一个分组方案的价值为所有组内的书权值和的乘积。

现在小 P 想知道对于所有分组方案,其价值的和是多少。由于这个数太大,所以小 P 只想知道它对 109+7 取模的结果。

两个分组方案不同当且仅当存在两本书在一个分组方案中被分进了同一组而另一个分组方案中不在同一组。

输入格式

第一行两个整数 n,m。

第二行 nm 个整数依次表示每本书的权值 ai。

输出格式

一行一个整数表示所有方案权值的总和。

样例一

input

3 1
2 3 4

output

85

样例二

input

2 2 
1 3 5 6

output

169

限制与约定

对于所有数据满足: 1≤n≤1500,1≤m≤100,0≤ai<109+7。

  • Subtask 1(10pts): 满足 n,m≤4。
  • Subtask 2(20pts): 满足 m=1。
  • Subtask 3(15pts): 满足 n≤100。
  • Subtask 4(15pts): 满足 n≤500。
  • Subtask 5(40pts): 满足 n≤1500。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 1
2 3 4
85

样例 2

2 2 
1 3 5 6
169