KBTU 파티

KBTU 졸업 파티에 여학생 $n$명 $D_1, D_2, \dots, D_n$과 남학생 $2n-1$명 $B_1, B_2, \dots, B_{2n-1}$이 참석했다. 여학생 $D_j$는 정확히 남학생 $B_1, B_2, \dots, B_{2j-1}$ (앞에서부터 $2j-1$명)과만 아는 사이다.

서로 아는 여학생과 남학생을 한 쌍으로 묶어 춤을 추게 하려고 한다. 정확히 $r$쌍을 고르되, 각 쌍은 서로 아는 사이여야 하고, 어떤 학생도 두 쌍 이상에 속할 수 없다(각 여학생과 각 남학생은 최대 한 쌍에만 포함된다). 이렇게 서로소인 $r$개의 쌍으로 이루어진 선택의 수를 구하여라. 두 선택은 이루는 쌍들의 집합이 다르면 서로 다른 것으로 센다.

공백으로 구분된 두 정수 $n$과 $r$ ($1 \le n, r \le 10^6$)이 주어진다.

가능한 선택의 수를 $2946859$로 나눈 나머지를 출력한다.