正の整数 n が与えられたときに、1, 2, ..., n を2つの集合に分割し、それぞれの合計値が同じになるような分割方法の数を求めます。
たとえば n = 7 の場合、合計が等しくなるように2つの集合に分割する方法は全部で4通りあります。
{1, 3, 4, 6} と {2, 5, 7}
{1, 2, 5, 6} と {3, 4, 7}
{1, 2, 4, 7} と {3, 5, 6}
{1, 6, 7} と {2, 3, 4, 5}
入力
入力は1行で、整数 n (1 ≤ n ≤ 500) が与えられます。
出力
で割った余りを出力してください。
例
