マークル木とは (paizaランク B 相当)

ハッシュ関数は様々なデータの要約・検証に使うことができます。そのうちのひとつがマークル木（マークルツリー）です。マークル木とは、ノードにハッシュ値をもつ二分木で、それぞれ親ノードには子ノードのハッシュ値を結合したものを入力として得られるハッシュ値が割り当てられています。特に、木構造の根の部分のハッシュ値をルートハッシュと呼びます。以下の例を参考にしてください。



本問では、マークル木におけるデータの要約をしてみましょう。

整数 N が与えられ、その後 2^N 個の文字列 d_i (1 ≦ i ≦ 2^N) が与えられます。以下のハッシュ関数 H を用いて、これらの文字列から計算されるルートハッシュ h を出力してください。なお、親ノードのハッシュ値 h_b を計算する際は、上の画像のように、隣同士の子ノードのハッシュ値 h_b0 と h_b1 を順番に文字列として結合させて得た新たな文字列を入力として計算してください。片方の子ノードがない場合、一つの子ノード h_b0 を複製して結合させた文字列を新たな入力とするやり方などがありますが、今回の問題で扱うマークル木は完全二分木のためそのような場合は起こりません。

文字列 s の長さを m として、

H(s) = (s の 1 文字目の文字コード * B1 + s の 2 文字目の文字コード * B2 + ... + s の m 文字目の文字コード * Bm) % mod

ただし、B = 10⁸+7, mod = 10⁹+7 とし、文字コードは ASCII に従って変換してください。