Компания из n человек решила сыграть в игру. Каждый человек может пойти в красную команду, может пойти в синюю команду, а может стать зрителем. Выборы всех людей независимы, каждый человек выбирает любой из 3 вариантов с равной вероятностью. Выигрывает команда, у которой больше игроков; в случае равенства — ничья. Пусть вероятность победы красной команды равна t. Найдите (t · 3ⁿ) mod p, где p — простое.

В единственной строке записаны два целых числа n и p (1 ≤ n ≤ 10¹⁸, 5 ≤ p < 10⁶, p — простое).

Выведите одно число — ответ на задачу.