No.1202 How to Eat Sweets
タグ : / 解いたユーザー数 32
作問者 :
PCTprobability
/ テスター :
hotman78
Problem Statement
There are $N$ packs of sweets. The packs are numbered from $1$ to $N$. Each pack of sweets contains $M$ cases that hold sweets (hereafter called sweet cases). The cases in each pack are numbered from $1$ to $M$. Here, the total number of sweets in a pack is defined as the sum of the numbers of sweets in the sweet cases contained in that pack. The number of sweets in sweet case $j$ of pack $i$ is $S_{i,j}$. It is guaranteed that $S_{i,j} \le S_{i-1,j}$ if $i \ge 2$, and $S_{i,j} \le S_{i,j-1}$ if $j \ge 2$. $P$-kun repeatedly performs one of the following operations until no sweets remain.
- Operation $1$: From every sweet case, eat $1$ sweet if the case contains any.
- Operation $2$: For every pack of sweets, eat all the sweets in the case containing the most sweets in that pack. If multiple cases in the pack contain the same largest number of sweets, eat from the one with the smallest case number among them.
- Operation $3$: Among all packs of sweets, eat all the sweets in the pack with the largest total number of sweets. If multiple packs have the same largest total, eat from the one with the smallest pack number among them.
Input
$N$ $M$
$S_{1,1}\ S_{1,2}\ \dots\ S_{1,M}$
$S_{2,1}\ S_{2,2}\ \dots\ S_{2,M}$
...
$S_{N,1}\ S_{N,2}\ \dots\ S_{N,M}$
- All inputs are integers.
- $1 \le N,M \le 1000=10^3$
- $1 \le S_{i,j} \le 1000000=10^6$
- $S_{i,j} \le S_{i-1,j}$ if $i \ge 2$
- $S_{i,j} \le S_{i,j-1}$ if $j \ge 2$
Output
Output the number of possible ways to perform the operations modulo $1000000007$, followed by a newline.
Sample
Sample 1
Input
2 3
4 3 2
3 2 1
Output
63
Sample 2
Input
5 2
100 99
98 97
96 95
94 93
92 91
Output
937854048
Output the answer modulo $1000000007$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。