OMC228(E)

点数: 500

Writer: Shota_1110

　すべて区別できる $1111$ 個の島があり，そのうち $1$ 個を本土と呼び，残りの $1110$ 個を離島と呼びます．これら $1111$ 個の島に対し以下のルールで橋を作ることを考えます．

～ルール～

• 橋は異なる $2$ つの島同士をつなぐものとし，また，どの異なる $2$ つの島についても「橋が $1$ つつながっている」か「橋がつながっていない」のいずれかが成り立つ．
• 任意の異なる $2$ つの島は，一方の島からもう一方の島まで $1$ 回以上橋をたどって移動することができる．

ルールにしたがって橋を作ったとき，すべての離島に対しその遠さを次のように定めることができます．

• 離島 $X$ に対し，本土から $X$ まで橋をたどって移動するときに橋を経由する回数の最小値を，$X$ の遠さとする．

　ここで，非負整数からなる長さ $1110$ の列 $A = (a_1, a_2, ..., a_{1110})$ であって $a_1 + a_2 + \cdots + a_{1110} = 1110$ なるものを定めます．この列 $A$ に対し，ルールにしたがった橋の作り方の中で次の条件をみたすものの総数を $f(A)$ と表します．

• 各 $i = 1, 2, ..., 1110$ について，遠さが $i$ である離島がちょうど $a_i$ 個存在する．

このような列 $A$ のうち，$f(A)\gt0$ なるものの中で，「$f(A)$ が $37$ で割り切れる最大の回数」が最大になるものを $A_0$ としたとき，$f(A_0)$ は $2$ で最大何回割り切れますか？ここで $A_0$ の存在は一意的であることが保証されます．