問題文

高橋君は 2 兆 (=2×10^{12}) 円が欲しいです。高橋君の現在の所持金は A 円であり、ある日に高橋君が t 円を持っているならその翌日には 高橋君の所持金は 1 + Kt 円増加します。

高橋君の所持金がはじめて 2 兆円以上になるのは何日後でしょうか。

入力例1

1000 300

出力例1

4

入力例2

6 2

出力例2

25

入力例3

567876543 0

出力例3

1999432123457

問題文

高橋君は N 日にわたってゲームをしています。i(1 ≦ i ≦ N) 日目には、a_i 回のゲームをします。

各ゲームの結果は、勝つか負けるかのどちらかです。

高橋君の i(1 ≦ i ≦ N) 日目の機嫌は、勝率によって定まり、i-1 日目までの勝率より i 日目までの勝率のほうが真に高かった場合、i 日目に機嫌をよくします。そうでない場合、i 日目に機嫌を悪くします。 ただし、i 日目までの勝率とは、i = 0のとき 0 、そうでないときは i 日目までにゲームで勝った回数の合計を i 日目までにゲームをした回数の合計で割った値を指します。

高橋君の機嫌は AtCoder 社の収益に直結するので、青木君は高橋君の機嫌が気になります。青木君は、高橋君が N 日間で合計 K 回ゲームに勝ったことを知っています。

青木君に代わって、高橋君の機嫌がよかった日数の最大値を求めてください。

入力例1

5 7
2
3
7
4
9

出力例1

3

入力例2

3 5
1
2
2

出力例2

1

入力例3

2 4
2
10

出力例3

1

入力例4

10 12
2
8
3
5
10
5
2
9
19
22

出力例4

7

問題文

\sqrt{N} の上 k 桁が a_1a_2...a_k となるような最小の正整数 N を求めてください。

ただし、\sqrt{N} の上 k 桁とは、\sqrt{N} の十進表記を、先頭につづく 0 と小数点を除いて上から読んだときの k 番目の数字までを並べた列を指します。 例えば、\sqrt{2} の上 5 桁は 14142 、\sqrt{100} の上 6 桁は 100000 です。

入力例1

1414

出力例1

2

入力例2

316

出力例2

10

入力例3

31415926535897932384626433

出力例3

9869604401089358618834491

問題文

各辺はに 1 から N(N-1)/2 までの相異なる重みがついているような N 頂点の無向完全グラフであり、 最小全域木で使われる辺の重みが小さいほうから順に A_1,A_2,...,A_{N-1} であるようなものの個数を 10^9+7 で割ったあまりを求めてください。

ただし、頂点の入れ替えでうつりあうようなグラフも異なるものとして数えます。

入力例1

3
1
2

出力例1

6

入力例2

5
1
2
4
6

出力例2

69120

入力例3

5
2
3
4
5

出力例3

0

入力例4

10
1
2
4
6
8
10
11
12
14

出力例4

837872061