Руководство автобусного предприятия в Екатеринбурге обеспокоено тем, что пассажиры не любят оплачивать свой проезд, покупая билет в автобусе. Чтобы решить эту проблему, позвали консультанта из Уральского университета. Этот консультант сказал, что он сам не покупает билеты в автобусе, потому что они редко оказываются счастливыми (билет называется счастливым, если в его номере сумма первой половины цифр равняется сумме второй половины цифр). Руководство задумалось, сколько билетов с номером длины N являются счастливыми. При N = 2 получается только 10 счастливых билетов (с номерами 00, 11, 22, 33, 44, 55, 66, 77, 88, 99). При N = 4 счастливых билетов уже 670. А сколько счастливых билетов для других значений N?

Помогите автобусному предприятию. Напишите программу, которая посчитает количество счастливых билетов, номер которых состоит из N цифр.

В единственной строке записано чётное число N — количество цифр в номере билета (2 ≤ N ≤ 8).

Выведите количество билетов, в номере которых сумма первой половины цифр равняется сумме второй половины цифр.