33889번 - 공중화장실 공리주의

문제

어떤 공중화장실에는 일렬로 나란히 놓인 소변기 $N$개가 있다. 우리가 공중화장실을 이용할 때, 말로 표현되지는 않지만 많은 사람들이 공유하는 은근한 감정이 존재한다. 그것은 바로 "옆 칸에 누가 있는 상황은 가능한 피하고 싶다"는 것.

당신은 군중심리학자로서, 화장실을 이용할 때의 이러한 감정을 수치로 정량화하는 데 성공했다. 화장실을 이용하는 사람 $p_i$가 느끼는 심리적 안정감 $s_i$는 다음과 같이 계산된다:

• 양옆에 모두 사람이 있는 경우: $s_i=0$
• 한쪽에만 사람이 있는 경우: $s_i=1$
• 양쪽 모두 비어 있는 경우: $s_i=2$

단, 양옆에 소변기가 존재하지 않는 칸은 비어 있는 것으로 간주한다.

오늘은 $M$명의 사람이 동시에 화장실에 입장해 각자 소변기를 사용하려고 한다. 당신은 화장실을 이용하는 사람들의 최대 다수가 최대의 행복을 누리도록 돕고 싶기 때문에, $M$명 모두가 느낄 심리적 안정감의 총합이 최대가 되게 하는 배치를 고민하고 있다. 이에 앞서, 이러한 배치의 경우의 수가 얼마나 많이 있을지 궁금해진 당신은 이를 미리 계산해 보기로 했다. 단, 동일한 소변기 집합이 배치에 사용되었다면 사람들의 순서가 바뀌더라도 같은 경우로 간주한다.

입력

첫 번째 줄에 화장실에 있는 소변기의 개수 $N$ $(2\leq N\leq 1,000円),ドル 화장실을 이용하는 사람 수 $M$ $(1\leq M \leq N)$이 공백으로 구분되어 주어진다.

출력

화장실을 이용하는 모든 사람들의 심리적 안정감이 총합이 최대가 되는 인원 배치의 경우의 수를 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.

제한

힌트