Ваше завдання полягає в тому, щоб підрахувати кількість способів, якими числа ~1,2,\ldots,n~ можна розділити на дві групи з однаковою сумою.

Наприклад, якщо n=7, є чотири рішення:

• {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 \le n \le 500~

Формат вхідних даних

Єдиний рядок містить ціле число ~n~.

Формат вихідних даних

Виведіть відповідь за модулем ~10^9+7~.

Приклад вхідних даних

7

Приклад вихідних даних

4