配列のハッシュ

n 個の数値が与えられたとき、それらすべての合計ハッシュ値を計算する問題です。配列 A のハッシュ値は以下の式で求められます:

このとき、127 の冪乗は前の計算結果に 127 をかけて順次求めていくほうが効率的です。また、最終的に求める剰余をあらかじめ各項ごとに取ってからすべてを合計しても、結果は同じになります。

入力

最初の行には整数 n (1 ≤ n ≤ 100 000) が 1 つ与えられます。

次の行には、スペース区切りで n 個の整数 (0 ≤ ≤ ) が与えられます。

出力

配列のハッシュ値を出力してください。

例