入力

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

N

• 1 行目には、文字列の長さを表す整数 N (1 ≦ N ≦ 1000) が与えられる。

出力

長さ N の文字列の「部分文字列」の個数を 1 行に出力せよ。出力の末尾に改行を入れること。

入力

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

N_A N_B
A_1 A_2 ... A_{N_A}
B_1 B_2 ... B_{N_B}

• 1 行目には、2 つの整数 N_A (1 ≦ N_A ≦ 10^5), N_B (1 ≦ N_B ≦ 10^5) が空白区切りで与えられる。これは、Ant さんのソースコードに N_A 個、Bug くんのソースコードに N_B 個のメタ構文変数が現れたということを表す。
• 2 行目には、Ant さんのソースコードに現れたメタ構文変数の番号を表す N_A 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_i (1 ≦ A_i ≦ 10^9) は、Ant さんのソースコードに A_i 番のメタ構文変数が現れることを表す。ただし、p \neq q のとき A_p \neq A_q であることが保証される。
• 3 行目には、Bug くんのソースコードに現れたメタ構文変数の番号を表す N_B 個の整数が空白区切りで与えられる。このうち i 番目の整数 B_i (1 ≦ B_i ≦ 10^9) は、Bug さんのソースコードに B_i 番のメタ構文変数が現れることを表す。ただし、p \neq q のとき B_p \neq B_q であることが保証される。

部分点

この問題には部分点が設定されている。

• N_A,N_B ≦ 1000 と A_i,B_i ≦ 10^5 を満たすテストケース全てに正解した場合は、40 点が与えられる。
• A_i,B_i ≦ 10^5 を満たすテストケース全てに正解した場合は、70 点が与えられる。

出力

Ant さんと Bug くんのソースコードに現れるメタ構文変数の集合の Jaccard 係数を 1 行に出力せよ。小数点以下何桁でも出力してよいが、10^{-6} を超える絶対誤差を含んではならない。出力の末尾に改行を入れること。

入力

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

Q
T_1 X_1
T_2 X_2
:
T_Q X_Q

• 1 行目には、クエリの個数を表す整数 Q (1 ≦ Q ≦ 200,000) が与えられる。
• 2 行目からの Q 行には、クエリの情報が与えられる。このうち i 行目では、2 つの整数 T_i (1 ≦ T_i ≦ 2), X_i (1 ≦ X_i ≦ 200,000) が空白区切りで与えられる。これは、
  • T_i = 1 の場合、「S に数 X_i を追加する」というクエリを表す。ただし、クエリを処理する前の S には X_i が含まれていないことが保証される。
  • T_i = 2 の場合、「S に含まれる数のうち X_i 番目に小さい数を答え、その数を S から削除する」というクエリを表す。ただし、クエリを処理する前の S に含まれる数の個数が X_i 個以上であることが保証される。

出力

タイプ 2 のクエリの個数を Q_2 とすると、出力は Q_2 行からなる。このうち i 行目には、タイプ 2 のクエリのうち i 番目のものに対する答えを出力せよ。出力の末尾にも改行を入れること。

入力

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

N
A_0 A_1 ... A_N
T

• 1 行目には、高橋君が見つけた多項式の次数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
• 2 行目には、N+1 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_{i-1} (0 ≦ A_{i-1} ≦ 10^9+6) は、P(i-1) の値を 1,000,000,007 (10^9+7) で割った余りを表す。
• 3 行目には、整数 T (1 ≦ T ≦ 10^9) が与えられる。これは、あなたが当てなければならない値が P(T) であることを表す。

部分点

この問題には部分点が設定されている。

• N ≦ 100 を満たすテストケース全てに正解した場合は、40 点が与えられる。
• N ≦ 3,000 を満たすテストケース全てに正解した場合は、80 点が与えられる。

出力

P(T) の値を 1,000,000,007 (10^9+7) で割った余りを 1 行に出力せよ。このような値は一意に定まることが保証される。出力の末尾に改行を入れること。