Вещи собраны, автобус приехал, и вот наши друзья уже на вокзале в ожидании своего поезда.

Заходя в вагон поезда, Михаил заметил странную наполовину закрашенную надпись — " Made in Po... ". Не обратив сильно внимания, он сел на свое место, и поезд тронулся.

Смотря в окно, Миша слушал музыку, абсолютно не общаясь со своими друзьями, потому что представлял, как уже на этой неделе поедет в Минск проведать свою подружку. Но вдруг поезд заехал в тоннель, и стало абсолютно темно. И не успев подумать, что автор условия оплошал, ведь на пути Минск-Витебск не было тоннеля, стало светло. Но после выезда из тоннеля Мишаня заметил, что все его друзья куда-то пропали. Наш герой решил походить по вагону, но не было ни души.

И вот, зайдя в тамбур, он увидел человека в черном капюшоне. Этот человек предложил Мишане победить его в своей игре, и тогда он пообещал отпустить его друзей.

В этой игре в самом начале дается массив натуральных чисел $$$a$$$ размером $$$n$$$ и целое число $$$k$$$.

В свой ход игрок должен придумать массив $$$c$$$ $$$(0 \leq c_i \leq k,$$$ $$$ \sum c_i = k)$$$ размером $$$n$$$. После этого он находит число $$$S = \sum a_i \cdot c_i$$$. И если данное число $$$S$$$, получалось в предыдущих ходах у кого-то из игроков, данный игрок проигрывает.

Поскольку Миша умный спортпрогер, он сразу понял, что ответ зависит от четности количества различных $$$S$$$, которые могут получиться. Поэтому он просит вас помочь ему найти количество различных $$$S$$$.