問題文

サイボウズの社員の間では、すごろくが流行っています。

社員が遊んでいるすごろくは N+1 マスからなり、それぞれのマスには進む順に番号 0, 1, ... N がつけられています。 スタートのマスの番号は 0 、ゴールのマスの番号は N です。

あなたは、このすごろくに慣れるために、一人で駒を動かす練習をしています。 実際に駒を動かす前に K 回のターンで進めるマスの数 a_i (1 \leq i \leq K) を決め、スタートのマスに駒を置きました。 以下のようなルールに従って、実際に駒を動かすことにしました。

i ターン目 (1 \leq i \leq K) に行う動作

• 駒を a_i マス進めてもまだゴールに到達しないときは、駒を a_i マス進める。
• 駒をちょうど a_i マス進めるとゴールに到着するときは、駒を a_i マス進めてゴールに到着し、残りのターンを行わずにゲームを終了する。
• 駒を a_i マス未満進めるだけでゴールに到達できるときは、ゴールまで x マスちょうどで到達できるとき、ゴールまで移動し、その後 a_i - x マス戻る。

N 、 K および a_i があたえられるので、最終的に (K ターンを全て終えるか、途中でゴールに到着しゲームを終了した時) 駒が置かれているマスの番号を求めてください。

制約

• 1 \leq N \leq 10^9
• 1 \leq K \leq 1000
• 1 \leq a_i \leq N (1 \leq i \leq K)

入力例 1

10 4
5 7 2 5

出力例 1

10

はじめに駒は 0 に置かれています。

• 1 ターン目に 5 が出たので、駒は 5 に動きます。
• 2 ターン目に 7 が出たので、駒は 10 に動き、まだ 2 マス動けるので、 8 に戻ります。
• 3 ターン目に 2 が出たので、駒は 10 に動き、ちょうどゴールに到着したので、ここで移動をやめます。

最終的に 10 に駒が置かれています。

入力例 2

10 4
5 7 3 5

出力例 2

6

入力例 3

20 7
12 5 5 15 2 10 20

出力例 3

1

問題文

リクルートホールディングスの社員の間では、数字パズルが流行っています。

社員が遊んでいる数字パズルは、縦 9 行、横 9 列のマスに 1 から 9 の数字を一つずつ書いていくものです。 ただし、書かれた数字が以下の条件を満たす必要があります。

• それぞれの行において、同じ数字は 2 度以上登場しない。
• それぞれの列において、同じ数字は 2 度以上登場しない。
• どのマスについても、そのマスからチェスのナイトの駒が 1 回で移動できる位置 (図参照) に、そのマスと同じ数字が書かれていない。

図. もしあなたが黒いマスにチェスのナイトの駒を置いていたならば、白い丸のある 8 箇所にのみ 1 回で移動できる。

あなたは、解答をチェックするプログラムを書くことを任されました。縦 9 行、横 9 列のマスにそれぞれ 1 から 9 の数字が書かれたものが与えられるので、それが上の条件を満たすかどうかチェックするプログラムを作成してください。

制約

• s_{ij} (1 \leq i, j \leq 9) は 1 から 9 の数字

入力例 1

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

出力例 1

Yes

3 つの条件すべてを満たしています。

入力例 2

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345679

出力例 2

No

最後の行に 9 が 2 つ含まれているので、1 つ目の条件を満たしません。同様に、2 つ目の条件も満たしていません。

入力例 3

123456789
234567891
345678912
456789123
567891234
678912345
789123456
912345678
891234567

出力例 3

No

上から 7 行目で左から 3 列目のマスと上から 8 行目で左から 1 列目のマスは、互いにチェスのナイトの駒が 1 手で 移動できます。しかしこれら 2 つのマスには同じ数字が書かれているので、 3 つ目の条件を満たしていません。

問題文

サイバーエージェントの社員の間では、クロスワードが流行っています。

今回作ろうとしているのは、2 行 2 列の 4 マスに文字を一つずつ入れ、各行を左から読んだとき、および各列を上から読んだ時に、 いずれも単語となるものです。ただし、文字の種類が多いので、この問題では一つの整数が一つの文字に対応しているものとします。

あなたは、文字の種類数 N と辞書に載っている M 個の単語が与えられます。 それぞれの文字は便宜上、 1 から N の整数で表されます。 辞書は M 行からなり、そのうち i 行目 (1 \leq i \leq M) には、整数 a_i と b_i が書かれています。 これは、1 文字目が a_i で 2 文字目が b_i である単語が存在することを意味しています。 同じ単語が辞書に複数回登場することはありません。

今、マスには何も書かれていないので、それぞれの文字を入れた時、各行各列を読んだときいずれも存在する単語となるようにしたいです。 ありうる文字の入れ方の総数を求めてください。ただし、同じ単語を複数回使用してもかまいません。

制約

• 1 \leq N \leq 300
• 1 \leq M \leq N \times N
• 1 \leq a_i, b_i \leq N (1 \leq i \leq M)
• (a_i, b_i) \neq (a_j, b_j) (1 \leq i < j \leq M)

入力例 1

3 4
1 2
2 1
3 1
2 3

出力例 1

5

ありうる文字の入れ方は、下図のように 5 通りあります。

入力例 2

4 10
1 1
1 2
1 3
2 1
2 2
2 4
3 3
3 4
4 1
4 3

出力例 2

47

問題文

数直線上に N 個の点があります。 i 番目 (1 \leq i \leq N) の点の座標は x_i です。

また、座標 p と座標 q の距離は |p-q| です。

Q 個のクエリが与えられます。 i 番目 (1 \leq i \leq Q) のクエリでは、数直線上の座標 t_i が与えられます。 この点から N 個の点への距離の総和を求めてください。

制約

• 1 \leq N \leq 100,000
• 1 \leq Q \leq 100,000
• -10^9 \leq x_i \leq 10^9 (1 \leq i \leq N)
• -10^9 \leq t_i \leq 10^9 (1 \leq i \leq Q)
• x_i < x_{i+1} (1 \leq i \leq N-1)

入力例 1

5 4
1 4 5 8 10
3
4
7
11

出力例 1

17
14
15
27

たとえば、1 番目のクエリでは t_1=3 が与えられます。この座標から N 個の点への距離の総和は、 |1-3| + |4-3| + |5-3| + |8-3| + |10-3| = 17 となります。

入力例 2

8 10
-499 -120 32 255 571 890 1011 1256
0
-200
2500
364
-117
50
-612
889
32
364

出力例 2

4634
5594
16604
4060
5102
4470
8292
4696
4506
4060

問題文

あなたはスライドパズルで遊んでいます。このパズルは、縦 N 行、横 N 列の正方形のマスが並んだ盤を使います。盤の上から i 行目、左から j 列目のマスは、 (i, j) と表されます。 盤の中のいくつかのマスには障害物が置かれています。(1 つも置かれていない場合もあります。) また、この盤の上でスライドさせて動かす駒は、盤の縦 K 行、横 K 列を占める大きさの正方形です。

この駒は、障害物が置かれているマスに重ならない場所に置くことができ、駒の一部が盤からはみ出したり、障害物と重なることがないように、上下左右の 4 方向に平行移動させることができます。

以下のようなクエリが Q 個与えられるので、それぞれのクエリを処理してください。

• 2 つのマス (r_1, c_1) と (r_2, c_2) が与えられる。駒の左上が (r_1, c_1) に重なるように置かれている状態から、駒の左上が (r_2, c_2) に重なるように置かれている状態まで、スライドすることだけで到達できるなら Yes、到達できないなら No を出力する。

制約

• 1 \leq N \leq 1000
• 1 \leq K \leq N
• K は整数である。
• 1 \leq Q \leq 10^5
• s_{ij} (1 \leq i, j \leq N) は . または # である。
• 1 \leq r_{i1}, c_{i1}, r_{i2}, c_{i2} \leq N-K+1 (1 \leq i \leq Q)
• 各クエリにおいて、(r_1, c_1) を左上とする大きさ K \times K の正方形および (r_2, c_2) を左上とする大きさ K \times K の正方形の領域には、障害物が存在しない。

入力例 1

5 2 5
..#..
.....
####.
.....
#....
1 1 1 4
1 1 1 1
1 4 4 2
4 2 4 4
4 2 4 3

出力例 1

No
Yes
No
Yes
Yes

例えば 4 番目のクエリは、駒を右方向に 2 マス分平行移動させることで、途中で障害物と重なることなく移動させることができます。 一方 1 番目のクエリでは、障害物が邪魔となって目的地まで駒を移動させることができません。

入力例 2

7 3 5
.......
.......
...#...
.......
.......
..#....
......#
2 1 1 1
1 1 1 5
3 1 4 4
5 4 1 5
3 1 3 5

出力例 2

Yes
No
No
Yes
No

問題文

ある町に、数列が大好きな黒猫と計算が大好きな狼が住んでいます。今日は、二人である数列をもとに計算をして遊ぶことにしました。

黒猫は、長さ N の整数列 {a_i} を持っていて、この数列の隣り合う項の間に + または \times を挿入した式を作り、狼がその値を計算しようとしています。 二人はこの整数列を使いできるだけ長く遊びたいので、作ることができる全ての式 (2^{N-1} 通りある) を作り、それらの式の値の合計を求めることにしました。

最終的に答えが合っているかどうかをチェックしたいので、二人はこれらの合計を 1,000,000,007 (= 10^9 + 7) で割ったあまりを求めるプログラムを作ることを、プログラミングコンテストで日々鍛錬を続けているあなたに頼んできました。

あなたはこの値を計算するプログラムを作ることで、二人を助けてください。

ただし、 \times は + よりも計算の優先順序が高いことに注意してください。

制約

• 1 \leq N \leq 10^5
• 1 \leq a_i \leq 10^9 (1 \leq i \leq N)
• a_i (1 \leq i \leq N) は整数である。

入力例 1

3
1 2 3

出力例 1

24

考えられる数式は、 1+2+3 と 1+2 \times 3 と 1 \times 2+3 と 1 \times 2 \times 3 の 4 種類です。 これらの式を計算すると、それぞれ答えは 6、7、5、6 となるので、合計は 6+7+5+6=24 です。

入力例 2

2
28055 35642

出力例 2

0

求める合計は 1000000007 (= 10^9+7) となるので、これを 10^9+7 で割ったあまりである 0 を出力します。

入力例 3

12
31415926 535897932 38462643 383279502 884197 169399375 105820974 944592307 81640628 620899862 803482534 21170679

出力例 3

626713706