Эмбер и Шторм играют в игру. Вначале, Эмбер выбирает помеченное дерево T на n вершинах, такое что степень каждой вершины не превосходит d. Затем Шторм выбирает две различные вершины u и v в этом дереве и выписывает номера вершин на пути из u в v как последовательность a1, a2... ak. Наконец Эмбер выбирает произвольный индекс i (1 ≤ i < k) и выполняет одну из следующих операций ровно один раз:
- перевернуть подотрезок [i + 1, k] и прибавить ai ко всем числам на нём. После этого последовательность приобретает вид a1, ... ai, ak + ai, ak - 1 + ai, ... ai + 1 + ai
- Заменить все числа на подотрезке [i + 1, k] на противоположные и прибавить ai к ним. После этого последователньость приобретает вид a1, ... ai, - ai + 1 + ai, - ai + 2 + ai, ... - ak + ai
Эмбер выигрывает, если после произведённой операции массив монотонно возрастает или убывает, иначе выигрывает Шторм.
Игра может быть представлена набором (T, u, v, i, op), где op — это «перевернуть» или «выполнить отрицаение» в зависимости от действия, которое Эмбер выполнил на последнем шаге. Найдите количество наборов, которые могут образоваться в результате оптимальной игры Эмбера и Шторма. Если они играют оптимально и у игрока есть несколько ходов, которые гарантируют победу, игрок может воспользоваться любым из них. Также если у игрока нет ни одного хода, гарантирующего победу, он может воспользоваться любым ходом.
Выведите ответ по модулю m.
Примечание
В первом тестовом примере существует только одно возможное дерево. Можно выбрать два пути: из 1 в 2 и из 2 в 1. Для обоих путей i может быть равно только 1, а op может принимать оба возможных значения. Поэтому ответ равен 4.
Во втором тестовом примере подходящих деревьев нет.
В третьем тестовом примере есть три возможных дерева.