Эмбер и Шторм играют в игру. Вначале, Эмбер выбирает помеченное дерево T на n вершинах, такое что степень каждой вершины не превосходит d. Затем Шторм выбирает две различные вершины u и v в этом дереве и выписывает номера вершин на пути из u в v как последовательность a₁, a₂... a_k. Наконец Эмбер выбирает произвольный индекс i (1 ≤ i < k) и выполняет одну из следующих операций ровно один раз:

• перевернуть подотрезок [i + 1, k] и прибавить a_i ко всем числам на нём. После этого последовательность приобретает вид a₁, ... a_i, a_k + a_i, a_k - 1 + a_i, ... a_i + 1 + a_i
• Заменить все числа на подотрезке [i + 1, k] на противоположные и прибавить a_i к ним. После этого последователньость приобретает вид a₁, ... a_i,  - a_i + 1 + a_i,  - a_i + 2 + a_i, ... - a_k + a_i

Эмбер выигрывает, если после произведённой операции массив монотонно возрастает или убывает, иначе выигрывает Шторм.

Игра может быть представлена набором (T, u, v, i, op), где op — это «перевернуть» или «выполнить отрицаение» в зависимости от действия, которое Эмбер выполнил на последнем шаге. Найдите количество наборов, которые могут образоваться в результате оптимальной игры Эмбера и Шторма. Если они играют оптимально и у игрока есть несколько ходов, которые гарантируют победу, игрок может воспользоваться любым из них. Также если у игрока нет ни одного хода, гарантирующего победу, он может воспользоваться любым ходом.

Выведите ответ по модулю m.