Чтобы повысить интерес студентов к своему предмету, некоторые преподаватели придумывают нестандартные творческие задания. Такие задания нравятся студентам гораздо больше скучных лекций.
В начале одной из лекций преподаватель написал мелом на доске два числа N и X. После этого он объявил студентам, что отпустит их с лекции, как только они назовут все числа Y в диапазоне 0 ≤ Y < 2N такие, что количество единиц в двоичном представлении побитовой суммы 
будет нечетным.
Поначалу студенты с энтузиазмом участвовали в выполнении задания, выкрикивая с мест ответы. Однако очень скоро они поняли, что уйти раньше времени с лекции не получится, потому что в задании кроется какой-то подвох...
Когда энтузиазм угас вовсе и над аудиторией повисла гробовая тишина, преподаватель пообещал зачёт автоматом тому, кто скажет, сколько всего существует подходящих значений Y в заданных ограничениях.
Помогите студентам решить эту задачу и сможете автоматом получить зачтённую задачу!
В единственной строке задаются числа N (1 ≤ N ≤ 100) и X (0 ≤ X ≤ 1018).
Выведите количество подходящих значений Y по модулю 109 + 3.
2 3
2
5 17
16
