早稲田大学プログラミングコンテスト2019

A - WAsedAC

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(100\) 点

問題文

WUPC 2019の開催を記念して、カトーくんは文字列 \(s\) をプレゼントとしてもらいました。

しかしながら、カトーくんは WA という文字列が嫌いなので、 WA という文字列がなくなるまで以下の行動をすることにしました。

文字列 \(s\) を先頭から見ていき、連続する2文字が WA である場合、これを AC という文字列に置換する。
1回の置換を行った場合、文字列の先頭から再び上記の行動を行い、置換が行われなかった場合、終了する。

カトーくんが行動を終了したときの文字列を答えよ。

制約

\(1 \leq |s| \leq 10^5\)
入力される文字列は英大文字のみで構成される。

入力

入力は以下の形式で標準入力から与えられる。

\(s\)

出力

カトーくんが行動を終了したときの文字列を1行に出力してください。

入力例 1

WASEDA

出力例 1

ACSEDA

入力例 2

WWA

出力例 2

ACC

この文字列に対してカトーくんは2回の置換を行います。1回目の置換によって文字列は WAC となり、2回目の置換によって文字列は ACC となります。

B - 10 puzzle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(100\) 点

問題文

高さ\(H\)、幅\(W\)のマス目がある。はじめ、\(i\)行\(j\)列のマスには\(0\)以上\(9\)以下の数\(A_{i,j}\)が書かれている。マス目中のマスは辺を共有するマスに隣接している。ここで、あるマスの部分集合が「連結」であるとは、集合中の全てのマスのペアについて、集合中の隣接するマスに移動することを繰り返して行き来できることを指す。

カトーくんは以下の操作を\(0\)回以上行うことができる。

ある「連結」なマスの部分集合を選び、集合中のマスに書かれている数の最大値を\(M\)とした時、その集合の全てのマスに書かれている数を\(2 \times M\)を\(10\)で割ったあまりに書き換える。

カトーくんはマス目の全てのマスに書かれた数を\(0\)にすることができるか判定せよ。また、\(0\)にすることができる場合、これを達成するために必要な最小の操作回数を求めよ。

制約

\(1 \leq H,W \leq 100\)
\(0 \leq A_{i,j} \leq 9\)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(H\) \(W\)
\(A_{1,1}\ A_{1,2}\ \dots\ A_{1,W}\)
\(A_{2,1}\ A_{2,2}\ \dots\ A_{2,W}\)
\(\vdots\)
\(A_{H,1}\ A_{H,2}\ \dots\ A_{H,W}\)

出力

全てのマスに書かれている数を\(0\)にすることが可能な場合、以下の形式でYesと最小の操作回数\(N\)を出力してください。

Yes \(N\)

また、不可能な場合Noを出力してください。

入力例 1

2 3
0 1 2
3 4 5

出力例 1

Yes 1

例えば、全てのマスを集合として選ぶと\(M=5\)となります。\(2 \times M=10\)となり\(10\)で割ったあまりは\(0\)であるため、全てのマスの数を\(0\)に書き換えます。よって、\(1\)回の操作で目的を達成することができました。

入力例 2

2 2
1 2
2 1

出力例 2

No

どのように操作を行っても目的を達成できません。

入力例 3

出力例 3

Yes 2

例えば、はじめに\(6\)が書かれている全てのマスを集合として選び（これは「連結」です）これに対して操作を行った後、全てのマスを集合として選び操作を行うと\(2\)回の操作で目的を達成できます。

入力例 4

出力例 4

Yes 4

C - Permutation City

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

\(N\) 頂点 \(M\) 辺の連結な無向グラフが与えられます。頂点には \(1\) から \(N\) まで番号がついており、与えられるグラフに多重辺や自己ループはありません。

以下の条件を満たすような長さ \(N\) の順列 \(p\) を1つ出力してください。

各 \(1 \leq i \leq N\) について、2頂点 \(i, p_i\) の距離 \(D(i, p_i)\)は 1 または 2 である。

条件を満たす順列は必ず存在することが証明できます。複数ある場合はどれを出力しても構いません。

2頂点\(u, v\)の距離 \(D(u, v)\)とは、頂点 \(u\) からグラフの辺をたどって頂点 \(v\) まで到達するパスのうち、パスに含まれる辺の数の最小値と定義されます。

制約

\(2 \leq N \leq 200000\)
\(N-1 \leq M \leq 200000\)
\(1 \leq u_i, v_i \leq N\) (\(1 \leq i \leq M)\)

与えられるグラフにおいて頂点 \(u_i\), \(v_i\) を結ぶ無向辺があることを示す。

入力から構成されるグラフは連結であり、多重辺および自己ループを含まない。
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\) \(M\)
\(u_1\) \(v_1\)
\(u_2\) \(v_2\)
\(\vdots\)
\(u_M\) \(v_M\)

出力

条件を満たす順列 \(p\) をスペース区切りで出力せよ。

入力例 1

2 1
1 2

出力例 1

2 1

2頂点の距離は \(D(1, 2) = D(2, 1) = 1\) であるため、条件を満たしています。

入力例 2

出力例 2

2 3 4 1

答えが複数考えられる場合は、どれを出力しても正解になります。

D - Choose Your Characters

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

カトー君と、友人であるシンヤ君は、昨年末に発売された、とある大人気アクションゲームを二人でプレイするのが大好きです。

このゲームには \(N\) 種類のキャラがおり、それぞれのキャラに \(1,2, \cdots ,N\) の番号が割り振られています。そして、お互いのプレイヤーが \(1\) キャラずつを選び、対戦します。また、それぞれのキャラには他のキャラに対する相性が存在しています。

相性は全部で \(3\) 種類あり、"有利"、"不利"、"五分"のいずれかです。

キャラ \(i\) がキャラ \(j\) に有利であるとき
- 相手がキャラ \(j\) を選んでいて、自分がキャラ \(i\) を選んだ場合、対戦を有利に進めることができます。
キャラ \(i\) がキャラ \(j\) に不利であるとき
- 相手がキャラ \(j\) を選んでいて、自分がキャラ \(i\) を選んだ場合に、苦戦を強いられてしまいます。
キャラ \(i\) とキャラ \(j\) が五分であるとき
- 相性に左右されない公平な対戦をすることができます。

また、キャラ \(i\) がキャラ \(j\) に有利であるときは、必ずキャラ \(j\) がキャラ \(i\) に不利となっています。

さて、カトー君は負けず嫌いなため、シンヤ君に負けないように一部のキャラに絞って練習をすることにしました。

具体的には、ある区間 \([L,R]\) を選択して、その区間内のキャラを練習します。

また、より有利に試合を進めるために、次の条件を満たす区間を選ぶことにしました。

相手がいかなるキャラを選んでも、そのキャラに対して五分、もしくは有利なキャラが少なくとも一体は存在する。ただし、相手と同じキャラはその候補から除外する。

普段は勉強で忙しいカトー君は、できるだけ練習するキャラの数を少なくしたいです。忙しいカトー君の代わりに、練習するキャラを選んであげてください。

制約

\(2 \leq N \leq 10^5\)
\(1 \leq M \leq \min(2 \times 10^5,N(N-1)/2)\)
- 有利不利の相性の個数を表す。
\(1 \leq a_i, b_i \leq N\)
- \(a_i \neq b_i\)
- キャラ \(a_i\) はキャラ \(b_i\) に有利であることを表す。
問題文の条件と矛盾する入力は与えられないことが保証される。すなわち、
- \(i \neq j\) ならば \((a_i,b_i) \neq (a_j,b_j) \) (同じ条件は二度出現しない)
- \(i \neq j\) ならば \((a_i,b_i) \neq (b_j,a_j) \) (正反対の条件が同時に入力されることはない)
が成り立つ。
入力される値はすべて整数である。
なお、入力で与えられなかった相性については、全て五分であることが保証される。

入力

入力は以下の形式で標準入力から与えられる。

\(N\)
\(M\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

出力

問題の条件を満たす最小の区間の両端 \(L,R\) \((L \leq R)\) をスペース区切りで出力せよ。幅が最小となる区間が複数存在する場合は、 \(L\) の値が最も小さいものを出力せよ。

問題の条件を満たすような区間がない場合は -1 を出力せよ。

\(L\) \(R\)

入力例 1

出力例 1

2 3

例えば、キャラ \(1\) と \(3\) に対してはキャラ \(2\) を、キャラ \(2\) に対してはキャラ \(3\) を選択することで、任意の相手キャラに対して五分以上の相性で対戦することができます。

入力例 2

出力例 2

1 3

例えば、キャラ \(1\) と \(2\) に対してはキャラ \(3\) を、キャラ \(3\) に対してはキャラ \(1\) を選択することで、任意の相手キャラに対して五分以上の相性で対戦することができます。

また、区間の中で、一度も選ばれないキャラが存在していても構いません。

入力例 3

出力例 3

-1

キャラ \(2\) に対して五分以上の相性となるキャラは存在しません。

入力例 4

出力例 4

1 3

E - Artist

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

ツバサくんの学科では、お絵描きが流行っています。ツバサくんは、すごく変わった絵を描くため周りの皆から「画伯」と呼ばれています。ツバサくんの絵の描き方とお手本の絵が与えられるので、彼がどんな絵を描くのか予想してみましょう。

絵の描き方：
絵は \(M \times N\) マスの長方形であり、上から \(i\) 行目、左から \(j\) 列目にあるマスを \((i,j)\) で表します。マス目の色は2次元配列 \(a\) で表され、 \(a_{ij}\) が 0 のとき白色、1 のとき黒色です。ツバサくんは、まず \(1 \leq x \leq M -1 \) および \(1 \leq y \leq N -1 \) を満たす \(1\) つのマス \((x,y)\) を選びます。その後、すべてのマス \((i,j)\) を、

\(1 \leq i \leq x\)，\(1 \leq j \leq y \)
\(1 \leq i \leq x\)，\(y \lt j \leq N \)
\(x \lt i \leq M\)，\(1 \leq j \leq y \)
\(x \lt i \leq M\)，\(y \lt j \leq N \)

で表される \(4\) つの長方形に切り分け、それぞれ \(180\) 度回転させます。最後に、それぞれの長方形を元のマスに戻して完成です。

例：
\(3 \times 3\) の長方形のお手本が以下のようであったとします。

101
010
100

ここで、ツバサくんがマス \((1,1)\) を選択した場合、以下のような4つの長方形に分割されます。

1|01
-+--
0|10
1|00

それぞれの長方形を \(180\) 度回転させると、以下のようになります。

1|10
-+--
1|00
0|01

最後にそれぞれの長方形を元のマスに戻すと、次のような絵が完成します。

110
100
001

そして、ツバサくんは次のようなことも言っていました。

操作の前後で、それぞれの行、列にある黒いマスの個数は変化しない

さて、ツバサくんが選択しうるマスの個数はいくつでしょうか。

制約

\(2 \leq M, N \leq 10^5\)
\(4 \leq M \times N \leq 5 \times 10^5\)
\(a_{ij}\) は 0 あるいは 1
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(M\) \(N\)
\(a_{11}\)\(\dots\)\(a_{1N}\)
\(\vdots\)
\(a_{M1}\)\(\dots\)\(a_{MN}\)

出力

選択しうるマスの個数を出力せよ。

入力例 1

出力例 1

ツバサくんが選択できるマスは \((1,1)\) のみです。

入力例 2

2 3
101
010

出力例 2

ツバサくんが選択できるマスは \((1,1)\) と \((1,2)\) の \(2\) つです。

入力例 3

16 26
00000000000000000000000000
00000000000000000000000000
00000000111111111111110000
00000011111111111111110000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00001111110000000000000000
00000011111111111111110000
00000000111111111111110000
00000000000000000000000000
00000000000000000000000000

出力例 3

ツバサくんが選択できるマスはありません。

F - RPG

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

カトーくんは、とあるRPGのシナリオを作っています。このRPGでは \(N\) 個の場面があり、各場面は既に「戦闘」か「空き地」のどちらかであると決まっています。また、 \(M\) 個の場面間をつなぐ移動通路があり、\(i\) 番目の通路は、場面 \(a_i\) から場面 \(b_i\) へ移動が可能です。最初、RPGの主人公であるシンヤくんは、場面 \(1\) にいて、自由に通路を移動し、場面 \(N\) に到達したらゲームクリアです。

シンヤくんには「元気」と「疲労」の2種類の状態があります。「元気」状態では戦闘に挑むことができますが、「疲労」状態では戦闘することができません。「疲労」状態で「戦闘」場面に到達するとゲームオーバーとなります。

シンヤくんは「元気」状態でゲームを開始します。「戦闘」場面を通過すると、疲れて「疲労」状態になります。「疲労」状態から「元気」状態に戻るためには「回復所」を通過する必要があります。

「回復所」は任意の「空き地」場面に設置することができます。場面 \(i \ (2 \leq i \leq N-1)\) に回復所を設置するコストは \(c_i\) です。

現在、「回復所」をどこに設置するかは決まっていません。そこでカトーくんは、以下の条件を満たすように、「回復所」を設置することにしました。

場面 \(1\) から動き始めたシンヤくんが場面 \(N\)に向かうどのような移動を選んでも、任意の「戦闘」場面から他の「戦闘」場面に達する間に、少なくとも1回は「回復所」を通過する。
ゲームクリア時のシンヤくんの状態は「疲労」でも「元気」でもよい。

以上の条件を満たすようにカトーくんが「回復所」を設置する際に必要なコストの合計の最小値を求めてください。どのように「回復所」を設置しても条件を満たすことができなければ、 -1 を出力してください。

制約

\(3 \leq N \leq 500\)
\(N-1 \leq M \leq 1000\)
\(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\)
- \(c_i = -1\) ならば、場面 \(i\) は「戦闘」場面である。
- \(c_i \geq 0\)ならば、場面 \(i\) は「空き地」場面であり、そこに「休憩所」を設置するコストは \(c_i\) である。
\(1 \leq a_i , b_i \leq N \ (1 \leq i \leq M)\)
- 場面 \(a_i\) から、場面 \(b_i\) への移動通路があることを示す。
\(N\) 頂点 \(M\) 辺の有向グラフとみたとき、全ての頂点に対し、頂点 \(1\) からのパスと、頂点 \(N\) へ向かうパスが存在する。また、閉路は存在しない。
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\) \(M\)
\(c_2\) \(c_3\) \(\dots\) \(c_{N-1}\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

出力

条件を満たすような「回復所」の設置コストの合計の最小値を出力してください。条件を満たすことができない場合は、 -1 を出力してください。

入力例 1

7 7
-1 100 10 1 -1
1 2
2 3
3 6
2 4
4 5
5 6
6 7

出力例 1

場面 \(3\) と場面 \(5\) を選ぶのが最適です。

入力例 2

出力例 2

-1

場面 \(2\) から場面 \(3\) の間に「休憩所」を設置することができません。

G - Teishoku

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(200\) 点

問題文

W大学の食堂では\(N\)種類の定食を提供しており、各定食は\(0,1, \cdots ,{N-1}\)の整数で表されます。

今、食堂には\(M\)人が順番待ちで並んでいます。誰がどの定食を頼んだかは数列\(A\)で表され、順番待ちの前から\(i\)番目の人が頼んだ定食は\(A_i\)です。

食堂では効率化のため、同時に1種類の定食のみを作り、同じ種類の定食を頼んだ順番待ちの人全員に定食を提供します。この時、まだ定食の提供されていない人 \(i\)について、その人よりも後ろに並んでいる人 \(j\ (i < j < M)\) に定食が提供された場合、人 \(i\) の不満度は人 \(j\) ひとりにつき 1 だけ上昇します。

食堂では\(N!\)通りある定食の提供手順のうち、今並んでいる\(M\)人の不満度の総和が最小になるような順序で定食を提供したいです。適切な順序で定食を提供した時の不満度の総和を出力してください。

制約

\(1 \leq N \leq 15\)
\(1 \leq M \leq 200000\)
\(0 \leq A_i \leq N-1\)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\) \(M\)
\(A_0\) \(A_1\) \(\dots\) \(A_{M-1}\)

出力

適切な順序で定食を提供した時の、\(M\)人の不満度の総和の最小値を出力してください。

入力例 1

2 5
0 1 0 0 1

出力例 1

定食\(0\)を先に提供した場合、\(2\)番目の人の不満度が\(2\)だけ上昇し、\(5\)番目の人の不満度は増加しないので、不満度の総和は\(2\)になります。
定食\(1\)を先に提供した場合、\(1\)番目の人の不満度が\(2\)だけ上昇し、\(3\)番目と\(4\)番目の人の不満度がそれぞれ\(1\)だけ上昇するので、不満度の総和は\(4\)になります。

したがって、定食\(0\)を先に提供し、そのあとに定食\(1\)を提供する事で、不満度の総和を最小化できます。

入力例 2

5 5
4 1 2 3 0

出力例 2

H - Doki Doki Programming Clubs!

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : \(200\) 点

問題文

W大学ではサークル活動が盛んで、 \(N\) 個の競技プログラミングサークルがあります。サークル \(i\ (0 \leq i \leq N-1)\) の部員の人数は \(K_i\) であり、その \(j\ (0 \leq j \leq K_i-1)\) 番目の部員のレートは \(A_{i,j}\) です。

毎日、どのサークルがパソコン室を使うかで言い争いになり、サークル同士は競技プログラミング対決で決着をつけます。対決はそれぞれのサークルの部員が順番に1対1の勝負を行いますが、人数が少ない方のサークルの部員は多い方の人数に合わせて、対決が終わるまでローテーションします。

サークル \(X\) とサークル \(Y\) の対決の「白熱度」は対決する部員のレートの積の総和で表されます。式で表すと、以下のようになります。

数列\(A_X,A_Y\)について、\(0 \leq j \leq \max(K_X,K_Y)-1\)における\(\sum{(A_{X,\ {j \mod K_X}} \times A_{Y,\ {j \mod K_Y}})}\)の値

今、対決が \(Q\) 回行われ、\(i\ (0 \leq i \leq Q-1)\) 番目の対決はサークル \(X_i\) とサークル \(Y_i\) の対決でした。それぞれの対決について、「白熱度」を求めてください。ただし、答えは非常に大きくなることがあるので、\(10^9+7\)で割ったあまりを答えること。

制約

\(2 \leq N \leq 200000\)
\(1 \leq K_i\)
\(\sum K_i \leq 200000\)
\(1 \leq A_{i,j} \leq 10^9\)
\(1 \leq Q \leq 200000\)
\(0 \leq X_i, Y_i \leq N-1\)
\(X_i \neq Y_i\)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\)
\(K_0\ A_{0,0}\ A_{0,1}\ \dots\ A_{0,K_0-1}\)
\(K_1\ A_{1,0}\ A_{1,1}\ \dots\ A_{1,K_1-1}\)
\(\vdots\)
\(K_{N-1}\ A_{{N-1},0}\ A_{{N-1},1}\ \dots\ A_{{N-1},K_{N-1}-1}\)
\(Q\)
\(X_0\ Y_0\)
\(X_1\ Y_1\)
\(\vdots\)
\(X_{Q-1}\ Y_{Q-1}\)

出力

それぞれのクエリに対して答えを\(10^9+7\)で割ったあまりを出力してください。

入力例 1

出力例 1

77
70
53

例えば、二つ目のクエリに対しては、数列\(A_0,A_2\)に注目し\(K_0=1,K_2=3\)より答えは\(A_{0,0} \times A_{2,0}+A_{0,0} \times A_{2,1}+A_{0,0} \times A_{2,2}=70\)となります。

三つ目のクエリに対しては、数列\(A_1,A_2\)に注目し\(K_1=2,K_2=3\)より答えは\(A_{1,0} \times A_{2,0}+A_{1,1} \times A_{2,1}+A_{1,0} \times A_{2,2}=53\)となります。

入力例 2

2
3 1000000000 999999999 999999998
10 1 2 3 4 5 6 7 8 9 10
1
0 1

出力例 2

999999571

\(10^9+7\)で割ったあまりを出力してください。

I - Ramen

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : \(300\) 点

問題文

東西に一直線に広がるW大学通りは、ラーメン店の激戦区です。多数の出店があり、出店後すぐに潰れる店もあれば、長続きする店もあります。

ラーメン大好きヤマダ君は、これらのお店についての記録を見つけました。記録内はW大学通りの過去から現在に至るまでの全店舗 \(N\) 店を網羅しており、ラーメン店 \(i\) それぞれについて、以下の情報が記載されていました。

W通り上での位置 \(d_i\)
開店日（最初の営業日） \(o_i\)
閉店日（最後の営業日） \(c_i\)
- ラーメン店 \(i\) が現在も営業を続けている場合、 \(c_i = -1\) です。
販売しているラーメンの美味しさ指数 \(x_i\)

しかし、全てのお店でのラーメンの販売価格 \(p_i\) の情報が欠けていました。お金の少ない学生にとって、販売価格は非常に重要です。困ったヤマダ君は、ラーメンに詳しいカトー君に相談すると、W大学通りでのラーメンの販売価格には以下のルールがあることを知りました。

ラーメン店 \(i\) での販売価格 \(p_i\) は、そのお店の開店日の前日にW大学通りで営業している任意のラーメン店 \(j\) について、 \(p_i \leq \min( p_j + |d_i - d_j|^2 , x_i )\) が成り立つような \(p_i\) の最大値である。
開店日前日に、W大学通りで営業しているお店がないときは \(p_i = x_i\)。

この情報を基に、\(N\) 件のラーメン店でのラーメンの販売価格を復元してください。

制約

\(1 \leq N \leq 10^5\)
\(0 \leq d_i \leq 10^6\)
\(1 \leq x_i \leq 10^{12}\)
\(1 \leq o_i \leq c_i \leq 10^5\) または \(c_i = -1\)
\(o_i \leq o_{i+1}\)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\)
\(o_1\) \(c_1\) \(d_1\) \(x_1\)
\(\vdots\)
\(o_N\) \(c_N\) \(d_N\) \(x_N\)

出力

\(N\) 行出力してください。 \(i\) 行目には、ラーメン店 \(i\) の販売価格を出力してください。

入力例 1

出力例 1

入力例 2

7
1 5 106 662268024587
2 -1 131 151663457616
2 5 967 750705741256
2 6 95 614802747834
6 8 690 117869535832
7 7 644 14107192103
9 10 992 767668177628

出力例 2

662268024587
151663457616
662268765908
614802747834
117869535832
14107192103
117869627036

入出力の値は非常に大きい場合があるので注意してください。

J - Color Ball

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(300\) 点

問題文

\(N\) 本の全て色が異なる筒があり、それぞれに筒と同じ色のボールが \(a_1\), \(a_2\), ..., \(a_N\)個入っています。全ての筒に入っているボールを合わせると \(M\) 個です。

筒の幅はボールちょうど1つ分です。空である筒はないものとします。

アヤコさんは次のような遊びを思いつきました。以下の条件を満たすように、筒からボールを出して入れ直すというものです。

各筒に入っているボールの数が初期状態から変化していないこと。
各筒に入っているボールの色は、その筒の色と異なること。

条件を満たすようなボールの入れ方は何通りあるでしょうか。\(10^9+7\) で割った余りを求めてください。

ただし、同色のボール同士の区別はしませんが、筒に入っているボールの色の順番を区別するものとします。

制約

\(1 \leq N \leq 2000\)
\(1 \leq M \leq 2000\)
\(1 \leq a_i \leq M\)
\(\sum a_i = M\)
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(N\) \(M\)
\(a_1\) \(a_2\) \(\dots\) \(a_N\)

出力

問題の答えを1行に出力せよ。

入力例 1

2 4
2 2

出力例 1

条件を満たすのは2つのボールを下図のように入れ替えるパターンのみなので、答えは1通りです。

入力例 2

3 5
2 2 1

出力例 2

下図のように、答えは4通りです。

入力例 3

4 15
2 2 1 10

出力例 3

どのようにボールを入れても条件を満たすことができません。