1-dən n-ə qədər bir çox tam ədədlər ardıcıllığı üçün, bu ardıcıllığı elə iki alt ardıcıllığa bölmək olar ki, bu alt ardıcıllıqların elementlərinin cəmi eyni olsun.

Məsələn, əgər n = 3, olarsa, {1, 2, 3} çoxluğunu elə alt çoxluqlara bölmək olar ki, onların elementlərinin cəmi eyni olsun:

• {3} və {1, 2}

Bu yeganə bölgü sayılır (yəni, əks ardıcıllıqda uyğun bölgü eyni sayılır, uyğun olaraq bölgülərin sayını artırmır).

Əgər n = 7 olarsa, onda {1, 2, 3, ..., 7} çoxluğunu dörd üsulla elə iki hissəyə bölmək olar ki, hər bir hissə eyni cəmi versin:

• {1, 6, 7} və {2, 3, 4, 5}
• {2, 5, 7} və {1, 3, 4, 6}
• {3, 4, 7} və {1, 2, 5, 6}
• {1, 2, 4, 7} və {3, 5, 6}

Verilmış n üçün sizin proqram 1–dən n-ə qədər tam ədədlər ehtiva edən çoxluğu alt çoxluqların elementlərinin cəmi eyni olan alt çoxluqlara ayırma variantlarının sayını hesablamalıdır. Əgər belə alt çoxluqlar yoxdursa, O verməli.

Sizin proqram cavabı hesablamalıdır, cavabı hazır cədvəldə axtarmamalıdır.

Giriş verilənləri

Giriş faylı yuxarıda deyildiyi kimi yeganə n tam ədədindən ibarət sətri ehtiva edir.

Çıxış verilənləri

Çıxış faylı yeganə ədəddən (cari {1, 2, ..., n} çoxluğunu neçə variatla elə alt çoxluqlara bölmək olar ki, alt çoxluqların elementlərinin cəmi eyni olasun) ibarət sətri ehtiva edir. Belə bir ayırma mümkün olmazsa, çıxış faylına 0 verməli.