問題
IOI 왕국에는 복도가 아주 긴 신전이 있다. 이 신전의 복도에는 N개의 등이 있으며 해가 지기 전에 등을 켠다.
매일 등을 켜는 일은 신전의 복사인 창환이가 하는데,
최근 좋지 않은 경제 사정으로 모든 등을 밝히는 것이 힘들어짐에 따라 사원의 장로는
창환이에게 불이 켜진 등이 연속된 L개를 넘지 않도록 이야기 하였다.
또한 사원의 복도가 너무 어두워지지 않도록 불이 꺼진 등이 연속된 M개를 넘지 않도록 당부하였다.
두수 L과 M 그리고 등의 개수 N이 주어질 때 창환이가 등을 밝히는 방법은 몇 가지가 될 것인지 구하시오.
輸入
등의 개수 N과 연속해서 켜지면 안되는 등의 수 L(연속으로 켜질 수 있는 등 L개미만),
연속해서 꺼지면 안되는 등의 수 M(연속으로 꺼질 수 있는 등 M개미만)이 공백으로 구분되어 주어진다.
입력제한은 2 ≤ N, L, M ≤ 1,000,000 이다.
輸出
창환이가 등을 켜는 방법의 수를 2009로 나눈 나머지를 출력한다.
範例
7 3 3
42
來源
comkiwer
需要登入才能撰寫程式碼。