괄호

올바른 괄호 문자열은 다음 규칙으로 재귀적으로 정의한다.

• 빈 문자열은 올바른 괄호 문자열이다.
• $X$와 $Y$가 올바른 괄호 문자열이면, $X Y$ ($X$와 $Y$를 이어 붙인 문자열)도 올바른 괄호 문자열이다.
• $X$가 올바른 괄호 문자열이면, $`(`X`)`$도 올바른 괄호 문자열이다.

모든 올바른 괄호 문자열은 위 규칙을 반복 적용하여 만들 수 있다.

괄호 문자열에 대해 다음 연산을 수행할 수 있다.

• 매번 $L \le R$을 만족하는 두 인덱스 $L$, $R$을 고른다. 이 연산은 $L$부터 $R$까지(양 끝 포함) 인덱스의 문자를 수정한다.
• 먼저 이 문자들의 순서를 뒤집는다.
• 그다음 각 문자를 반대 문자로 바꾼다. 즉, 구간 안의 '('는 ')'가 되고, ')'는 '('가 된다.

괄호 문자열의 값은 이를 올바른 괄호 문자열로 바꾸는 데 필요한 연산 횟수의 최솟값이다. 불가능하면 값은 $10^{100}$이다.

예를 들어, "()(("의 값은 $1$이고, "()()"의 값은 $0$이며, "((("의 값은 $10^{100}$이다.

정수 $n$이 주어진다. 각 $1 \le i \le n$에 대해, 길이가 $n$이고 값이 $i$인 서로 다른 괄호 문자열의 개수 $A_i$를 구한 뒤, $\sum_{i = 0}^{n} ((i + 1) \cdot A_i)$의 값을 계산하라.

답이 매우 클 수 있으므로, 주어진 정수 $m$으로 나눈 나머지를 출력한다.

첫째 줄에 두 정수 $n$, $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^9$)이 주어진다.

답을 한 정수로 출력한다.