Задача Звезда Смерти

Описание

В первой строке входного файла даны два целых числа: N - число планет в Галактике, M - число фабрик, которые Федерация намерена построить (1 <= N <= 1400, 2 < M < 6). Во второй строке входного файла дана последовательность шестнадцатеричных цифр (0..9, A..F), которая представляет собой зашифрованную карту гипертуннелей. Для того, чтобы расшифровать ее, надо заменить каждую цифру ее двоичным представлением (имейте в виду, что если оно короче четырех цифр, его нужно дополнить нулями слева), а затем взять только первые цифр, а остальная часть последовательности должна быть удалена.

Оставшаяся последовательность - это описание гипертуннелей в следующем порядке:


где каждой паре (a-b) соответствует ровно одна цифра в последовательности, которая равна 1, если существует туннель из a в b и 0 в противном случае (то есть существует гипертуннель из b в a ).

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

В первой строке входного файла даны два целых числа: N - число планет в Галактике, M - число фабрик, которые Федерация намерена построить (1 <= N <= 1400, 2 < M < 6). Во второй строке входного файла дана последовательность шестнадцатеричных цифр (0..9, A..F), которая представляет собой зашифрованную карту гипертуннелей. Для того, чтобы расшифровать ее, надо заменить каждую цифру ее двоичным представлением (имейте в виду, что если оно короче четырех цифр, его нужно дополнить нулями слева), а затем взять только первые цифр, а остальная часть последовательности должна быть удалена.

Оставшаяся последовательность - это описание гипертуннелей в следующем порядке:


где каждой паре (a-b) соответствует ровно одна цифра в последовательности, которая равна 1, если существует туннель из a в b и 0 в противном случае (то есть существует гипертуннель из b в a ).

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

Выведите одно целое число - количество способов выбрать расположение фабрик. И да пребудет с вами Сила!