평범한 서수

집합, 집합, 집합. 수학의 모든 것은 결국 집합이다. 자연수도 집합으로 나타낼 수 있다. 예를 들어 수 $0$은 공집합 $\{\}$로 나타낸다. 수 $1$은 $\{\{\}\}$로 나타낸다.

그렇다면 $2$는 어떻게 나타낼까? $\{\{\},\{\{\}\}\}$를 보자. 이것은 공집합과 $\{\{\}\}$를 모두 원소로 가지는 집합이다. 이 표현이 $2$로 좋은 이유는 두 가지다. 첫째, $0$과 $1$은 $2$의 원소다. 둘째, $0$과 $1$은 $2$의 부분집합이기도 하다.

일반적으로 $N>0$이면, 수 $N$은 집합 $\{0,1,\dots,N-1\}$로 나타낸다. 이때 $0,1,\dots,N-1$의 표현도 같은 방식으로 재귀적으로 적용한다. 예를 들면 다음과 같다.

$\begin{aligned} 3 &= \{0,1,2\} \\ &= \{\{\},\{0\},\{0,1\}\} \\ &= \{\{\},\{\{\}\},\{\{\},\{0\}\}\} \\ &= \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\} \end{aligned}$

따라서 각 $0\le i<N$에 대해 $i$는 $N$의 원소이면서 동시에 $N$의 부분집합이다. 또 다른 좋은 성질은 $N$을 나타내는 집합의 크기도 $N$이라는 점이다. 그러나 이런 집합을 적는 데 드는 문자 수는 그리 좋지 않다. 자연수 $N\ge 0$이 주어졌을 때, 위 방식으로 $N$을 나타내는 집합을 적는 데 중괄호와 쉼표가 몇 개 필요한가?

좀 더 정확히 말하면, $f(N)$을 $N$을 나타내는 집합을 적는 데 필요한 괄호와 쉼표의 개수라고 하자. $f(N)$은 매우 클 수 있으므로, 어떤 양의 정수 $M$에 대해 $f(N)$을 $M$으로 나눈 나머지를 구하라.

입력은 위에서 설명한 두 정수 $N$ ($0\le N<2^{63}$)과 $M$ ($1\le M<2^{31}$)이다.

$f(N)$을 $M$으로 나눈 나머지를 출력한다. 즉, $f(N)$을 $M$으로 나누었을 때 남는 값이다.