У медведя Василия есть большая квадратная таблица белого цвета, составленная из n строк и n столбцов. Вокруг этой таблицы очерчена граница черной краской.
Пример изначальной таблицы при n = 5. Медведь Василий хочет ровно за k ходов покрасить свою квадратную таблицу. Каждый ход — это последовательность действий:
- Медведь выбирает некоторый квадрат внутри своей таблицы, причем вокруг квадрата должна должна быть очерчена граница черной краской, а также внутри квадрата не должно быть ячейки, закрашенной в черный цвет. Количество ячеек в квадрате должно быть не меньше 2.
- Медведь выбирает внутри выбранного квадрата некоторую строку и некоторый столбец. Далее он закрашивает каждую ячейку этой строки и этого столбца внутри выбранного квадрата. После описанной операции прямоугольники, образованные границей квадрата и только что закрашенными ячейками, должны являться квадратами ненулевой площади.
Пример корректной покраски при n = 7 и k = 2. Медведь уже знает числа n и k. Помогите ему — найдите количество способов покрасить его квадрат ровно за k действий. Два способа покраски называются различными, если полученные таблицы будут различаться цветом хотя бы в одной ячейке. Так как ответ может быть большим, выведите его остаток от деления на 7340033.
Выходные данные
Для каждого теста из входных данных выведите ответ на задачу по модулю 7340033. Ответы для тестов выводите в том порядке, в котором тесты заданы во входных данных.
Примечание
Все возможные покраски для теста n = 7 и k = 2:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1 0
1 1
3 0
3 1
2 0
2 1
3 2
7 2
|
1
0
1
1
1
0
0
4
|