405134: GYM101804 G Greatest IME

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Greatest IMEtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Many programming competitions are done in teams, usually having $$$3$$$ contestants per team, and the contestants from the same group have to sit on adjacent chairs to be able to discuss problems and pair-program.

(The second greatest) IME (Instituto de Matemática e Estatística), has a lot of teams. For this year's tryouts, they decided that each team will have $$$3$$$ contestants, the chairs will be positioned in a row and each contestant will be able to sit anywhere they want (but the contestants of the same team must sit adjacent and no two contestants can sit on the same chair).

There are $$$n$$$ teams competing and $$$c$$$ chairs positioned in a row.

Since the number of ways that contestants may sit is too large and they don't know how to calculate it, they asked students from (the greatest) IME (Instituto Militar de Engenharia), to calculate it for them.

Two ways are considered distinct if at least one contestant is sitting on a different chair on both ways.

As the answer can be very large, so you must print it modulo $$$10^9+7$$$.

Input

The first line and only line contains two integers, $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 10^5$$$, $$$3 \times n \leq c \leq 3 \times 10^5$$$) — the number of teams and the number of chairs, respectively.

Output

Print the number of ways the contestants can sit modulo $$$10^9+7$$$.

ExamplesInput
1 4
Output
12
Input
2 8
Output
432
Input
3 11
Output
12960

加入题单

上一题 下一题 算法标签: