E. ZS и Парадокс дней рождения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кодер ZS недавно узнал об интересной идее, так называемом Парадоксе дней рождения. Он утверждает, что среди произвольной группы из 23 человек с примерно 50% вероятностью найдутся двое, дни рождения которых совпадают. Кодер ZS нашел это очень интересным, и решил проверить это на жителях Удайлэнда.

Продолжительность года в Удайлэнде равна 2n дням. Кодер ZS хочет расспросить k жителей Удайлэнда, день рождения каждого из которых совпадает с одним из 2n дней (с равной вероятностью). ZS'а интересует вероятность того, что хотя бы двое из них родились в один и тот же день.

Кодер ZS знает, что ответ можно записать в виде несократимой дроби . Он хочет найти значения A и B (ему не нравится работать с вещественными числами). Поможете ему?

Входные данные

Первая и единственная строка содержит два целых числа n и k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 1018), означающих, что в продолжительность года — 2n дней, а Кодер ZS хочет расспросить ровно k людей.

Выходные данные

Если вероятность того, что хотя бы двое из k людей имеют совпадающий день рождения в году продолжительностью 2n дней, равняется (A ≥ 0, B ≥ 1, ), выведите A и B в единственной строке.

Так как эти числа могут быть очень большими, выведите остатки от их деления на 106 + 3. Заметьте, что A и B должны быть взаимно простыми до того, как берутся их остатки от деления на 106 + 3.

Примеры
Входные данные
3 2
Выходные данные
1 8
Входные данные
1 3
Выходные данные
1 1
Входные данные
4 3
Выходные данные
23 128
Примечание

В первом примере из условия, продолжительность года в Удайлэнде равна 23 = 8 дней. Вероятность того, что 2 человека имеют день рождения в один и тот же день среди группы из 2 человек, очевидно равна , поэтому A = 1, B = 8.

Во втором примере из условия, в Удайлэнде всего 21 = 2 дня в году, но группа состоит из 3 человек, поэтому в любом случае у двоих из них совпадут дни рождения. Таким образом, вероятность равна 1 и A = B = 1.