9016: K-electron Shell
[만든사람 : 10hour]
문제 설명
가상의 원자 $A$가 있다. 이 원자는 $N$개의 전자껍질을 갖는데, 이 원자의 전자는
그 반발력이너무 강해 다음의 두 가지 반발 규칙을 따른다.
1. 각 전자껍질에는 전자를 최대 1개까지 올릴 수 있다.
2. 각 전자들은 반발력으로 인해 서로 너무 가까이 있을 수 없는데.
구체적으로 전자가 놓인 두 위치 $i$, $j$ 에 대해 $|i-j| \ge K+1$를 만족해야 한다.
여러분은 $N$, $K$가 주어졌고 전자를 아무 개수나 놓아도 좋다고 했을 때 가능한 전자 배치의 수를 구해야 한다.
단, 답이 커질 수 있으니 $10^9+7$로 나눈 나머지를 대신 출력한다.
그 반발력이너무 강해 다음의 두 가지 반발 규칙을 따른다.
1. 각 전자껍질에는 전자를 최대 1개까지 올릴 수 있다.
2. 각 전자들은 반발력으로 인해 서로 너무 가까이 있을 수 없는데.
구체적으로 전자가 놓인 두 위치 $i$, $j$ 에 대해 $|i-j| \ge K+1$를 만족해야 한다.
여러분은 $N$, $K$가 주어졌고 전자를 아무 개수나 놓아도 좋다고 했을 때 가능한 전자 배치의 수를 구해야 한다.
단, 답이 커질 수 있으니 $10^9+7$로 나눈 나머지를 대신 출력한다.
입력 설명
첫 번째 줄에 두 정수 $N$, $K$가 주어진다 $(1 \le N \le 10^6,\ \ 0 \le K \le N)$
출력 설명
r가능한 전자 배치의 가짓수를 $1\;000\;000\;007$로 나눈 나머지를 출력한다.
입력 예시 Copy
100 50
출력 예시 Copy
1275