У доброжелательного Даниила есть несколько яблок. В силу своей природной доброжелательности, каждый раз, когда он встречает какого-либо своего друга, он смотрит на яблоки, которые у него есть и отдает другу половину.

Но Даниил не одинаково любит всех своих друзей, поэтому некоторым из них он отдает половину яблока, а некоторым — половину имеющихся у него яблок. При этом с глазомером у Даниила не так хорошо, как со щедростью, и делить яблоки более, чем на две части, у него не получается. Поэтому, если он встречает друга, а у него нецелое число яблок, то он вынужден отдать половину яблока.

Утром у Даниила было \(n\) яблок, а за день Даниил встретил \(k\) друзей. Выясните, сколько яблок у него могло остаться вечером.

Во многих языках программирования есть функции, которые отвечают за заполнение всего массива или некоторой его части определенным значением. В языке Pascal это функция fillchar(), в Java — Arrays.fill(), в C++ — memset(). В новом языке программирования J# появилась функция mark(), которая умеет работать только с массивами логического типа.

Функция mark, вызванная от двух параметров \(a\) и \(b\), присваивает всем элементам массива с индексами от \(a\) до \(b\) включительно значение true, Так, если взять массив длины \(4\), элементы которого нумеруются с единицы и все значения в котором изначально равны false, и выполнить с ним операции mark(1, 3) и mark(2, 4), то весь массив окажется заполнен значениями true.

Одним из первых заданий для тех, кто начинает изучать J#, является написание программы, содержащей ровно \(M\) операций mark, и полностью заполняющей значениями true массив длины \(N\), изначально заполненный значениями false.

Вы быстро справились с этим заданием, и теперь задумались: сколькими различными способами это можно сделать? Различными считаются такие способы, в которых \(i\)-я операция mark в двух программах запущена с разными параметрами хотя бы для одного \(i\) от \(1\) до \(M\). Это число может быть большим, поэтому требуется посчитать его по модулю \(10^9 + 7\).

В новых процессорах, проектируемых корпорацией MBI, для работы со строками выделен отдельный сопроцессор. Этому сопроцессору можно передать строку, состоящую из строчных символов латинского алфавита, и программу, описывающую обработку строки. После этого процессор задумается и, через долю секунды, вернет результат обработки строки.

Работа еще не завершена, поэтому пока что он умеет обрабатывать строки только одним способом. Строка, которую ему передают на ввод, должна состоять из \(2^k\) символов, а программа обработки этой строки — из \(2^k \ − \ 1\) чисел, каждое из которых является нулем или единицей.

Если строка, поданная на вход сопроцессору, состоит из одного символа, то результат обработки равен этой же строке. Если строка длиннее, то выполняются следующие действия.

Сначала он разобьет строку на две части равной длины, а программу — на три части. При этом длины первых двух частей программы будут равны между собой, а третьей частью будет последнее число программы. После этого первая половина строки превратится в результат ее обработки первой частью программы, а вторая — в результат ее обработки второй частью программы. После этого, если оставшееся число равно нулю, вторая половина строки будет дописана справа к первой, если же оно равно единице — первая половина будет дописана справа ко второй.

Так, например, если на вход сопроцессору подана строка «abcd» и программа (0, 1, 1), то результатом обработки будет строка «dcab».

Вам поступило предложение принять участие в его тестировании. Отказаться от такого лестного предложения вы не смогли, поэтому теперь вам необходимо научиться составлять программу для сопроцессора, с помощью которой он преобразует строку \(S\) в строку \(T\), или же определять, что такой программы не существует.

На прошлом уроке английского Пете задали домашнее задание. Оно заключалось в разгадывании ребусов. Каждый ребус — это последовательность картинок. С двух сторон от каждой картинки могут располагаться апострофы. Каждая картинка обозначает некоторое слово. Предположим, что перед некоторой картинкой нарисовано \(i\) апострофов, а после нее \(j\) апострофов. Это значит, что у слова, которое сопоставляется картинке, необходимо убрать \(i\) букв с начала и \(j\) с конца, а оставшуюся его часть записать вместо картинки и апострофов. Так необходимо сделать с каждой картинкой и окружающими ее апострофами. После этого нужно «склеить» получившиеся кусочки в одно слово. Оно и будет разгадкой ребуса.

У Пети нет проблем с тем, чтобы сопоставить каждой картинке слово. Но ему очень лень заниматься отбрасыванием лишних букв и склеиванием слов. Поэтому он попросил вас помочь ему. Дана строка, которая состоит из маленьких латинских букв, апострофов (символов с кодом 39), а также пробелов, которые разделяют слова. Апостроф относиться к некоторому слову, если между ними нет пробела. Если апостроф стоит слева от слова, то у него необходимо убрать одну букву с начала, если справа — с конца. Потом необходимо склеить все слова в одно.

Например, пусть дана строчка «team ’ ’ ’ ’ school ’ ’ olympiad’ ’ ’». В первом слове ничего изменять не надо, так как к нему не относится ни один апостроф. Во втором необходимо убрать первые четыре буквы и получить «ol», из третьего слова получится «ymp». После скеливания трех кусочков получим строку «teamolymp».

Каждый год профессор Иванов ездит в Африку с целью изучить племена, которые там проживают. В этом году он ездил в гости к племени тив. Профессор довольно быстро научился понимать их язык, выучил многие их обряды, однако, он никак не мог понять записанные цифрами тив числа. Как и мы, члены племени используют позиционную систему счисления с основанием 10. Но цифры в племени тив обозначают символами, не похожими на обычные цифры от 0 до 9.

Профессор обозначил эти символы буквами от ‘a’ до ‘j’, но не может понять, какой цифре соответствует какой символ. Тогда вождь племени дал ему список из n неотрицательных чисел, записанных без ведущих нулей, и сказал, что числа в нем отсортированы строго по возрастанию.

Помогите профессору восстановить по этому списку какое-нибудь соответствие символов цифрам.