Чтобы космический корабль мог взлететь, каждому члену экипажа нужно выдать билетик. На каждом билетике должна быть написана последовательность из n цифр, где n - четное положительное число.

Даниил считает билет супер-счастливым, если выполняются два свойства:

• Сумма первых n/2 цифр равна сумме последних n/2 цифр.
• Сумма цифр на четных позициях равна сумме цифр на нечетных позициях.

Помогите Даниилу посчитать количество различных супер-счастливых билетиков по модулю 998244353.

Формат входных данных

В первой строке дано одно число n - длина билетика (2 ≤ n ≤ 200000). Гарантируется, что n чётное.

Формат выходных данных

Выведите количество супер-счастливых билетиков длины n по модулю 998244353.

Пример