No.834 Random Walk Trip
タグ : / 解いたユーザー数 56
作問者 :
leaf_1415
/ テスター :
tempura_pp
Problem Statement
There are $N$ countries in the world, called country $1,$ country $2,$ $\ldots,$ country $N$.
A-kun, who lives in country $1$, is planning to travel around the world over $M$ days.
Feeling that simply traveling would be boring, A-kun decided to determine the course of his trip using a coin.
The trip consists of day $1$, day $2$, $\ldots,$ day $M$, and A-kun is in country $1$ at the beginning of day $1$.
Let country $x$ be the country where A-kun is at the beginning of day $i$. A-kun's actions on day $i$ are as follows.
(1) He tosses a coin and observes whether it lands heads or tails.
(2) If it lands heads: if $x > 1$, A-kun moves to country $x-1$; if $x = 1$, A-kun does nothing.
If it lands tails: if $x < N$, A-kun moves to country $x+1$; if $x = N$, A-kun does nothing.
(3) Let country $y$ be the country where A-kun is after step (2) above. A-kun writes $y$ on page $i$ of his travel journal.
Let $a_i$ be the integer written on page $i$ of the travel journal after day $M$ has ended.
Find the total number of possible sequences $a_1, a_2, \ldots, a_M$ that satisfy $a_M = 1$.
Since the answer can be very large, output the remainder when the answer is divided by $10^9+7$.
Input
$N\ M$
The input satisfies the following constraints.
$1 \leq N \leq 10^6$
$1 \leq M \leq 10^6$
$N,\ M$ are both integers
Output
Output on one line the number of sequences satisfying the conditions, modulo $10^9+7$. Print a newline at the end.
Sample
Sample 1
Input
2 3
Output
4
Suppose the coin tosses, in order from day 1, are (tails, tails, heads).
Then he moves from country 1 to country 2 on day 1, stays in country 2 on day 2, and returns from country 2 to country 1 on day 3, so the sequence $\{a_i\}$ is $2, 2, 1$.
Similarly,
for (tails, heads, heads), the sequence $\{a_i\}$ is $2, 1, 1$;
for (heads, heads, heads), the sequence $\{a_i\}$ is $1, 1, 1$;
for (heads, tails, heads), the sequence $\{a_i\}$ is $1, 2, 1$,
and these are all the sequences satisfying the conditions of the problem.
Therefore, the answer is $4$.
Sample 2
Input
1 2
Output
1
The only possible sequence $\{a_i\}$ is $1, 1$.
Sample 3
Input
16 21
Output
352716
Sample 4
Input
1000000 1000000
Output
996692777
Output the remainder when the answer is divided by $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。