KBTU Party

Time limit2sMemory limit128 MB

Summary

Count the ways to choose r disjoint acquainted girl-boy pairs when girl j knows exactly the first 2j-1 boys, modulo 2946859.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math, Number theory
Solved: No attempts yet

Problem

At the KBTU graduation party there are $n$ girls $D_1, D_2, \dots, D_n$ and $2n-1$ boys $B_1, B_2, \dots, B_{2n-1}$ . Girl $D_j$ is acquainted with exactly the boys $B_1, B_2, \dots, B_{2j-1}$ (the first $2j-1$ boys).

We want to pick exactly $r$ dancing pairs. Each pair consists of one girl and one boy who are acquainted, and no student may belong to more than one pair (every girl and every boy appears in at most one chosen pair). Count the number of ways to choose such a set of $r$ pairwise-disjoint acquainted pairs. Two choices are considered different if their sets of pairs differ.

Input

Two integers $n$ and $r$ ( $1 \le n, r \le 10^6$ ) separated by a space.

Output

Print the number of ways, taken modulo $2946859$ .

Examples1

Example 1
Input
```
3 2
```
Expected output
```
18
```