Problem:


Score : 500 points

Problem Statement

We have a grid of squares with N rows and M columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. We will choose K of the squares and put a piece on each of them.

If we place the K pieces on squares (x_1, y_1), (x_2, y_2), ..., and (x_K, y_K), the cost of this arrangement is computed as:

\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)

Find the sum of the costs of all possible arrangements of the pieces. Since this value can be tremendous, print it modulo 10^9+7.

We consider two arrangements of the pieces different if and only if there is a square that contains a piece in one of the arrangements but not in the other.

Constraints

2 \leq N \times M \leq 2 \times 10^5

2 \leq K \leq N \times M

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the sum of the costs of all possible arrangements of the pieces, modulo 10^9+7.

Sample Input 1

2 2 2

Sample Output 1

8

There are six possible arrangements of the pieces, as follows:

((1,1),(1,2)), with the cost |1-1|+|1-2| = 1

((1,1),(2,1)), with the cost |1-2|+|1-1| = 1

((1,1),(2,2)), with the cost |1-2|+|1-2| = 2

((1,2),(2,1)), with the cost |1-2|+|2-1| = 2

((1,2),(2,2)), with the cost |1-2|+|2-2| = 1

((2,1),(2,2)), with the cost |2-2|+|1-2| = 1

The sum of these costs is 8.

Sample Input 2

4 5 4

Sample Output 2

87210

Sample Input 3

100 100 5000

Sample Output 3

817260251

Be sure to print the sum modulo 10^9+7.



Sample input:
2 2 2


Sample output:
8

Submission status: Runtime Error

Solution code:
git add d.py
git commit -m "AC: atcoder/2017/1230_abc084/d.py"

 OSX  L 1.49  ~/src/git…/ykmc/con…/atc…/2017/1230_abc084   master ? ↑4 
 ykmc@ykmcnoMacBook-Pro  git add d.py                                                                                                       ✔  18:12:38
git commit -m "AC: atcoder/2017/1230_abc084/d.py"
[master fc278fb] AC: atcoder/2017/1230_abc084/d.py
 1 file changed, 43 insertions(+)
 create mode 100644 atcoder/2017/1230_abc084/d.py

 OSX  L 1.48  ~/src/git…/ykmc/con…/atc…/2017/1230_abc084   master ↑5 
 ykmc@ykmcnoMacBook-Pro  git push                                                                                                           ✔  18:12:41
Enumerating objects: 52, done.
Counting objects: 100% (52/52), done.
Delta compression using up to 16 threads
Compressing objects: 100% (24/24), done.
Writing objects: 100% (50/50), 4.24 KiB | 1.06 MiB/s, done.
Total 50 (delta 5), reused 0 (delta 0)
remote: Resolving deltas: 100% (5/5), done.
To ssh://github.com/ykmc/contest.git
   2d719c6..fc278fb  master -> master

 OSX  L 1.46  ~/src/git…/ykmc/con…/atc…/2017/1230_abc084   master 
 ykmc@ykmcnoMacBook-Pro  git status                                                                                                         ✔  18:12:50
On branch master
Your branch is up to date with 'origin/master'.

nothing to commit, working tree clean

 OSX  L 1.47  ~/src/git…/ykmc/con…/atc…/2017/1230_abc084   master 
 ykmc@ykmcnoMacBook-Pro  cd ../../                                                                                                          ✔  18:13:33

 OSX  L 1.46  ~/src/git…/ykmc/con…/atcoder   master 
 ykmc@ykmcnoMacBook-Pro  ls -la                                                                                                             ✔  18:13:35
total 816
drwxr-xr-x  7 ykmc  staff     224  4  4 17:34 .
drwxr-xr-x  6 ykmc  staff     192  4  4 15:46 ..
drwxr-xr-x  3 ykmc  staff      96  4  4 16:22 2013
drwxr-xr-x  3 ykmc  staff      96  4  4 16:59 2016
drwxr-xr-x  3 ykmc  staff      96  4  4 17:34 2017
drwxr-xr-x  3 ykmc  staff      96  4  1 21:00 2019
-rw-r--r--  1 ykmc  staff  414415  4  3 20:33 problem-models.json

 OSX  L 1.46  ~/src/git…/ykmc/con…/atcoder   master 
 ykmc@ykmcnoMacBook-Pro  cd 2019                                                                                                            ✔  18:13:36

 OSX  L 1.46  ~/src/git…/ykmc/con…/atc…/2019   master 
 ykmc@ykmcnoMacBook-Pro  ls -la                                                                                                             ✔  18:13:38
total 0
drwxr-xr-x  3 ykmc  staff   96  4  1 21:00 .
drwxr-xr-x  7 ykmc  staff  224  4  4 17:34 ..
drwxr-xr-x  9 ykmc  staff  288  4  4 15:47 0519_abc126

 OSX  L 1.46  ~/src/git…/ykmc/con…/atc…/2019   master 
 ykmc@ykmcnoMacBook-Pro  mkdir 0525_abc127                                                                                                  ✔  18:13:39

 OSX  L 1.77  ~/src/git…/ykmc/con…/atc…/2019   master 
 ykmc@ykmcnoMacBook-Pro  cd 0525_abc127                                                                                                     ✔  18:13:49

 OSX  L 1.76  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master 
 ykmc@ykmcnoMacBook-Pro  ls -la                                                                                                             ✔  18:13:52
total 0
drwxr-xr-x  2 ykmc  staff   64  4  4 18:13 .
drwxr-xr-x  4 ykmc  staff  128  4  4 18:13 ..

 OSX  L 1.76  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py init                                                                              ✔  18:13:54
https://atcoder.jp/contests/abc127/tasks/abc127_a
https://atcoder.jp/contests/abc127/tasks/abc127_b
https://atcoder.jp/contests/abc127/tasks/abc127_c
https://atcoder.jp/contests/abc127/tasks/abc127_d
https://atcoder.jp/contests/abc127/tasks/abc127_e
https://atcoder.jp/contests/abc127/tasks/abc127_f

 OSX  L 1.72  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  ls -la test                                                                                                        ✔  18:14:03
total 272
drwxr-xr-x  36 ykmc  staff  1152  4  4 18:14 .
drwxr-xr-x   9 ykmc  staff   288  4  4 18:14 ..
-rw-r--r--   1 ykmc  staff     8  4  4 18:14 a_1_in.txt
-rw-r--r--   1 ykmc  staff     5  4  4 18:14 a_1_out.txt
-rw-r--r--   1 ykmc  staff     8  4  4 18:14 a_2_in.txt
-rw-r--r--   1 ykmc  staff     4  4  4 18:14 a_2_out.txt
-rw-r--r--   1 ykmc  staff     7  4  4 18:14 a_3_in.txt
-rw-r--r--   1 ykmc  staff     3  4  4 18:14 a_3_out.txt
-rw-r--r--   1 ykmc  staff     9  4  4 18:14 b_1_in.txt
-rw-r--r--   1 ykmc  staff    52  4  4 18:14 b_1_out.txt
-rw-r--r--   1 ykmc  staff     9  4  4 18:14 b_2_in.txt
-rw-r--r--   1 ykmc  staff    75  4  4 18:14 b_2_out.txt
-rw-r--r--   1 ykmc  staff    15  4  4 18:14 c_1_in.txt
-rw-r--r--   1 ykmc  staff     3  4  4 18:14 c_1_out.txt
-rw-r--r--   1 ykmc  staff    21  4  4 18:14 c_2_in.txt
-rw-r--r--   1 ykmc  staff     3  4  4 18:14 c_2_out.txt
-rw-r--r--   1 ykmc  staff    20  4  4 18:14 c_3_in.txt
-rw-r--r--   1 ykmc  staff     8  4  4 18:14 c_3_out.txt
-rw-r--r--   1 ykmc  staff    22  4  4 18:14 d_1_in.txt
-rw-r--r--   1 ykmc  staff     4  4  4 18:14 d_1_out.txt
-rw-r--r--   1 ykmc  staff    49  4  4 18:14 d_2_in.txt
-rw-r--r--   1 ykmc  staff     5  4  4 18:14 d_2_out.txt
-rw-r--r--   1 ykmc  staff    30  4  4 18:14 d_3_in.txt
-rw-r--r--   1 ykmc  staff     5  4  4 18:14 d_3_out.txt
-rw-r--r--   1 ykmc  staff    71  4  4 18:14 d_4_in.txt
-rw-r--r--   1 ykmc  staff    13  4  4 18:14 d_4_out.txt
-rw-r--r--   1 ykmc  staff     7  4  4 18:14 e_1_in.txt
-rw-r--r--   1 ykmc  staff     3  4  4 18:14 e_1_out.txt
-rw-r--r--   1 ykmc  staff     7  4  4 18:14 e_2_in.txt
-rw-r--r--   1 ykmc  staff     7  4  4 18:14 e_2_out.txt
-rw-r--r--   1 ykmc  staff    14  4  4 18:14 e_3_in.txt
-rw-r--r--   1 ykmc  staff    11  4  4 18:14 e_3_out.txt
-rw-r--r--   1 ykmc  staff    24  4  4 18:14 f_1_in.txt
-rw-r--r--   1 ykmc  staff    11  4  4 18:14 f_1_out.txt
-rw-r--r--   1 ykmc  staff    84  4  4 18:14 f_2_in.txt
-rw-r--r--   1 ykmc  staff    24  4  4 18:14 f_2_out.txt

 OSX  L 1.71  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py git                                                                               ✔  18:14:05
git add test
git commit -m "init: atcoder/2019/0525_abc127"

 OSX  L 1.71  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  git add test                                                                                                       ✔  18:14:09
git commit -m "init: atcoder/2019/0525_abc127"
[master ef67016] init: atcoder/2019/0525_abc127
 34 files changed, 81 insertions(+)
 create mode 100644 atcoder/2019/0525_abc127/test/a_1_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/a_1_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/a_2_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/a_2_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/a_3_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/a_3_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/b_1_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/b_1_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/b_2_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/b_2_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/c_1_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/c_1_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/c_2_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/c_2_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/c_3_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/c_3_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_1_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_1_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_2_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_2_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_3_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_3_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_4_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/d_4_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/e_1_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/e_1_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/e_2_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/e_2_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/e_3_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/e_3_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/f_1_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/f_1_out.txt
 create mode 100644 atcoder/2019/0525_abc127/test/f_2_in.txt
 create mode 100644 atcoder/2019/0525_abc127/test/f_2_out.txt

 OSX  L 1.73  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  git status                                                                                                         ✔  18:14:12
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        a.py
        b.py
        c.py
        d.py
        e.py
        f.py

nothing added to commit but untracked files present (use "git add" to track)

 OSX  L 1.73  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  git push                                                                                                           ✔  18:14:14
Enumerating objects: 40, done.
Counting objects: 100% (40/40), done.
Delta compression using up to 16 threads
Compressing objects: 100% (9/9), done.
Writing objects: 100% (37/37), 2.02 KiB | 295.00 KiB/s, done.
Total 37 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To ssh://github.com/ykmc/contest.git
   fc278fb..ef67016  master -> master

 OSX  L 1.79  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  code *.py                                                                                                          ✔  18:14:20

 OSX  L 1.77  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  ls -la                                                                                                             ✔  18:14:42
total 48
drwxr-xr-x   9 ykmc  staff   288  4  4 18:14 .
drwxr-xr-x   4 ykmc  staff   128  4  4 18:13 ..
-rw-r--r--   1 ykmc  staff   331  4  4 18:15 a.py
-rw-r--r--   1 ykmc  staff   331  4  4 18:15 b.py
-rw-r--r--   1 ykmc  staff   331  4  4 18:15 c.py
-rw-r--r--   1 ykmc  staff   331  4  4 18:15 d.py
-rw-r--r--   1 ykmc  staff   331  4  4 18:15 e.py
-rw-r--r--   1 ykmc  staff   331  4  4 18:15 f.py
drwxr-xr-x  36 ykmc  staff  1152  4  4 18:14 test

 OSX  L 1.76  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test a.py                                                                         ✔  18:15:16
a_1 : AC
---input----------------
30 100
---output---------------
100
---answer---------------
100

a_2 : AC
---input----------------
12 100
---output---------------
50
---answer---------------
50

a_3 : AC
---input----------------
0 100
---output---------------
0
---answer---------------
0


 OSX  L 1.31  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py git a.py                                                                          ✔  20:58:08
git add a.py
git commit -m "AC: atcoder/2019/0525_abc127/a.py"

 OSX  L 1.29  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  git add a.py                                                                                                       ✔  20:58:28
git commit -m "AC: atcoder/2019/0525_abc127/a.py"
[master 840ca63] AC: atcoder/2019/0525_abc127/a.py
 1 file changed, 23 insertions(+)
 create mode 100644 atcoder/2019/0525_abc127/a.py

 OSX  L 1.33  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  git push                                                                                                           ✔  20:58:33
Enumerating objects: 10, done.
Counting objects: 100% (10/10), done.
Delta compression using up to 16 threads
Compressing objects: 100% (6/6), done.
Writing objects: 100% (6/6), 657 bytes | 657.00 KiB/s, done.
Total 6 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To ssh://github.com/ykmc/contest.git
   ef67016..840ca63  master -> master

 OSX  L 1.34  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test b.py                                                                         ✔  20:58:40
b_1 : AC
---input----------------
2 10 20
---output---------------
30
50
90
170
330
650
1290
2570
5130
10250
---answer---------------
30
50
90
170
330
650
1290
2570
5130
10250

b_2 : AC
---input----------------
4 40 60
---output---------------
200
760
3000
11960
47800
191160
764600
3058360
12233400
48933560
---answer---------------
200
760
3000
11960
47800
191160
764600
3058360
12233400
48933560


 OSX  L 1.42  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py git b.py                                                                          ✔  21:00:13
git add b.py
git commit -m "AC: atcoder/2019/0525_abc127/b.py"

 OSX  L 1.41  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  git add b.py                                                                                                       ✔  21:00:35
git commit -m "AC: atcoder/2019/0525_abc127/b.py"
[master 0883696] AC: atcoder/2019/0525_abc127/b.py
 1 file changed, 19 insertions(+)
 create mode 100644 atcoder/2019/0525_abc127/b.py

 OSX  L 1.41  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  git push                                                                                                           ✔  21:00:43
Enumerating objects: 10, done.
Counting objects: 100% (10/10), done.
Delta compression using up to 16 threads
Compressing objects: 100% (6/6), done.
Writing objects: 100% (6/6), 676 bytes | 676.00 KiB/s, done.
Total 6 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To ssh://github.com/ykmc/contest.git
   840ca63..0883696  master -> master

 OSX  L 1.41  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test c.py                                                                         ✔  21:00:52
c_1 : WA
---input----------------
4 2
1 3
2 4
---output---------------
-2
---answer---------------
2

c_2 : WA
---input----------------
10 3
3 6
5 7
6 9
---output---------------
-6
---answer---------------
1

c_3 : WA
---input----------------
100000 1
1 100000
---output---------------
-1
---answer---------------
100000


 OSX  L 1.42  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test c.py                                                                         ✔  21:03:16
c_1 : WA
---input----------------
4 2
1 3
2 4
---output---------------
1
---answer---------------
2

c_2 : WA
---input----------------
10 3
3 6
5 7
6 9
---output---------------
0
---answer---------------
1

c_3 : WA
---input----------------
100000 1
1 100000
---output---------------
99999
---answer---------------
100000


 OSX  L 1.37  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test c.py                                                                         ✔  21:03:43
c_1 : AC
---input----------------
4 2
1 3
2 4
---output---------------
2
---answer---------------
2

c_2 : AC
---input----------------
10 3
3 6
5 7
6 9
---output---------------
1
---answer---------------
1

c_3 : AC
---input----------------
100000 1
1 100000
---output---------------
100000
---answer---------------
100000


 OSX  L 1.39  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test c.py                                                                         ✔  21:03:53
c_1 : AC
---input----------------
4 2
1 3
2 4
---output---------------
2
---answer---------------
2

c_2 : AC
---input----------------
10 3
3 6
5 7
6 9
---output---------------
1
---answer---------------
1

c_3 : AC
---input----------------
100000 1
1 100000
---output---------------
100000
---answer---------------
100000


 OSX  L 1.40  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py git c.py                                                                          ✔  21:04:36
git add c.py
git commit -m "AC: atcoder/2019/0525_abc127/c.py"

 OSX  L 1.38  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  git add c.py                                                                                                       ✔  21:05:26
git commit -m "AC: atcoder/2019/0525_abc127/c.py"
[master 697f776] AC: atcoder/2019/0525_abc127/c.py
 1 file changed, 23 insertions(+)
 create mode 100644 atcoder/2019/0525_abc127/c.py

 OSX  L 1.38  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  git push                                                                                                           ✔  21:05:30
Enumerating objects: 10, done.
Counting objects: 100% (10/10), done.
Delta compression using up to 16 threads
Compressing objects: 100% (6/6), done.
Writing objects: 100% (6/6), 758 bytes | 758.00 KiB/s, done.
Total 6 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To ssh://github.com/ykmc/contest.git
   0883696..697f776  master -> master

 OSX  L 1.37  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                         ✔  21:05:37
d_1 : WA
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
[1, 4, 5]
[(2, 3)]
---answer---------------
14

d_2 : WA
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
[1, 4, 5, 5, 7, 8, 13, 33, 52, 100]
[(3, 10)]
---answer---------------
338

d_3 : WA
---input----------------
3 2
100 100 100
3 99
3 99
---output---------------
[100, 100, 100]
[(3, 99)]
---answer---------------
300

d_4 : WA
---input----------------
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
---output---------------
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[(3, 1000000000)]
---answer---------------
10000000001


 OSX  L 1.42  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                         ✔  21:14:12
d_1 : WA
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
[1, 4, 5]
[(1, 5), (2, 3)]
---answer---------------
14

d_2 : WA
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
[1, 4, 5, 5, 7, 8, 13, 33, 52, 100]
[(1, 4), (3, 10), (4, 30)]
---answer---------------
338

d_3 : WA
---input----------------
3 2
100 100 100
3 99
3 99
---output---------------
[100, 100, 100]
[(3, 99), (3, 99)]
---answer---------------
300

d_4 : WA
---input----------------
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
---output---------------
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[(3, 1000000000), (3, 1000000000), (4, 1000000000)]
---answer---------------
10000000001


 OSX  L 1.45  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                         ✔  21:14:36
d_1 : WA
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
[1, 4, 5]
[(2, 3), (1, 5)]
---answer---------------
14

d_2 : WA
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
[1, 4, 5, 5, 7, 8, 13, 33, 52, 100]
[(1, 4), (3, 10), (4, 30)]
---answer---------------
338

d_3 : WA
---input----------------
3 2
100 100 100
3 99
3 99
---output---------------
[100, 100, 100]
[(3, 99), (3, 99)]
---answer---------------
300

d_4 : WA
---input----------------
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
---output---------------
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[(3, 1000000000), (4, 1000000000), (3, 1000000000)]
---answer---------------
10000000001


 OSX  L 1.57  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                         ✔  21:17:13
  File "d.py", line 20
    BC.sort(key = lambda x:x[1]、reverse=True)
                                      ^
SyntaxError: invalid character in identifier
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'd.py']' returned non-zero exit status 1.

 OSX  L 1.64  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                       1 ↵  21:18:15
d_1 : WA
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
[1, 4, 5]
[(1, 5), (2, 3)]
---answer---------------
14

d_2 : WA
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
[1, 4, 5, 5, 7, 8, 13, 33, 52, 100]
[(4, 30), (3, 10), (1, 4)]
---answer---------------
338

d_3 : WA
---input----------------
3 2
100 100 100
3 99
3 99
---output---------------
[100, 100, 100]
[(3, 99), (3, 99)]
---answer---------------
300

d_4 : WA
---input----------------
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
---output---------------
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[(3, 1000000000), (4, 1000000000), (3, 1000000000)]
---answer---------------
10000000001


 OSX  L 1.71  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                         ✔  21:18:58
Traceback (most recent call last):
  File "d.py", line 25, in <module>
    for j in b:
TypeError: 'int' object is not iterable
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'd.py']' returned non-zero exit status 1.

 OSX  L 1.75  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                       1 ↵  21:20:03
d_1 : WA
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
[5, 3, 3]
---answer---------------
14

d_2 : WA
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
[30, 30, 30, 30, 10, 10, 10, 4, 0, 0]
---answer---------------
338

Traceback (most recent call last):
  File "d.py", line 26, in <module>
    C[i+j] = c
IndexError: list assignment index out of range
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'd.py']' returned non-zero exit status 1.

 OSX  L 1.64  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                       1 ↵  21:20:50
d_1 : AC
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
14
---answer---------------
14

d_2 : AC
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
338
---answer---------------
338

Traceback (most recent call last):
  File "d.py", line 26, in <module>
    X[i+j] = c
IndexError: list assignment index out of range
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'd.py']' returned non-zero exit status 1.

 OSX  L 1.62  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test d.py                                                                       1 ↵  21:22:12
d_1 : AC
---input----------------
3 2
5 1 4
2 3
1 5
---output---------------
14
---answer---------------
14

d_2 : AC
---input----------------
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
---output---------------
338
---answer---------------
338

d_3 : AC
---input----------------
3 2
100 100 100
3 99
3 99
---output---------------
300
---answer---------------
300

d_4 : AC
---input----------------
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
---output---------------
10000000001
---answer---------------
10000000001


 OSX  L 1.57  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  git status                                                                                                         ✔  21:22:43
On branch master
Your branch is up to date with 'origin/master'.

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        d.py
        e.py
        f.py

nothing added to commit but untracked files present (use "git add" to track)

 OSX  L 1.42  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py git d.py                                                                          ✔  21:33:41
git add d.py
git commit -m "AC: atcoder/2019/0525_abc127/d.py"

 OSX  L 1.43  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? 
 ykmc@ykmcnoMacBook-Pro  git add d.py                                                                                                       ✔  21:33:46
git commit -m "AC: atcoder/2019/0525_abc127/d.py"
[master d4a33da] AC: atcoder/2019/0525_abc127/d.py
 1 file changed, 36 insertions(+)
 create mode 100644 atcoder/2019/0525_abc127/d.py

 OSX  L 1.44  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                         ✔  21:33:50
  File "e.py", line 35
    for d in range(1:M):
                    ^
SyntaxError: invalid syntax
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'e.py']' returned non-zero exit status 1.

 OSX  L 1.38  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                       1 ↵  21:38:27
  File "e.py", line 40
    for d in range(1:M):
                    ^
SyntaxError: invalid syntax
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'e.py']' returned non-zero exit status 1.

 OSX  L 1.35  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                       1 ↵  21:39:43
Traceback (most recent call last):
  File "e.py", line 23, in <module>
    fact,finv,inv = init_fact(200010,modulo)
NameError: name 'modulo' is not defined
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'e.py']' returned non-zero exit status 1.

 OSX  L 1.37  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                       1 ↵  21:39:53
Traceback (most recent call last):
  File "e.py", line 34, in <module>
    t = d * nCr(N*M-2, K-2)
TypeError: nCr() missing 3 required positional arguments: 'mod', 'fact', and 'finv'
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'e.py']' returned non-zero exit status 1.

 OSX  L 1.36  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                       1 ↵  21:40:11
e_1 : AC
---input----------------
2 2 2
---output---------------
8
---answer---------------
8

e_2 : AC
---input----------------
4 5 4
---output---------------
87210
---answer---------------
87210

e_3 : AC
---input----------------
100 100 5000
---output---------------
817260251
---answer---------------
817260251


 OSX  L 1.35  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                         ✔  21:40:49
Traceback (most recent call last):
  File "e.py", line 31, in <module>
    Combination = Combination(200010, mod)
TypeError: __init__() takes 2 positional arguments but 3 were given
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'e.py']' returned non-zero exit status 1.

 OSX  L 1.39  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                       1 ↵  10:42:42
Traceback (most recent call last):
  File "e.py", line 36, in <module>
    t = d * Combination.nCr(N*M-2, K-2)
TypeError: nCr() takes 2 positional arguments but 3 were given
Traceback (most recent call last):
  File "../../../tools/atcoder.py", line 339, in <module>
    exec_test(args[2])
  File "../../../tools/atcoder.py", line 201, in exec_test
    res = subprocess.run(cmd, input=data_in.encode(), check=True, stdout=subprocess.PIPE)
  File "/Users/ykmc/.anyenv/envs/pyenv/versions/3.8.0/lib/python3.8/subprocess.py", line 512, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['python', 'e.py']' returned non-zero exit status 1.

 OSX  L 1.44  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro  python ../../../tools/atcoder.py test e.py                                                                       1 ↵  10:43:04
e_1 : AC
---input----------------
2 2 2
---output---------------
8
---answer---------------
8

e_2 : AC
---input----------------
4 5 4
---output---------------
87210
---answer---------------
87210

e_3 : AC
---input----------------
100 100 5000
---output---------------
817260251
---answer---------------
817260251


 OSX  L 1.44  ~/src/git…/ykmc/con…/atc…/2019/0525_abc127   master ? ↑1 
 ykmc@ykmcnoMacBook-Pro                                                                                                                     ✔  10:43:17