2つの等しい集合

正の整数 n が与えられたときに、1, 2, ..., n を2つの集合に分割し、それぞれの合計値が同じになるような分割方法の数を求めます。

入力

入力は1行で、整数 n (1 ≤ n ≤ 500) が与えられます。

出力

で割った余りを出力してください。

例