Time Limit: 1s
Memory Limit: 256MB
The director of a hospital want to schedule a working plan for a nurse in a given period of N consecutive days 1,..., N. Due to the policy of the hospital, each nurse cannot work all the days 1,..., N. Instead, there must be days off in which the nurse need to take a rest. A working plan is a sequence of disjoint working periods. A working period of a nurse is defined to be a sequence of consecutive days on which the nurse must work and the length of the working period is the number of consecutive days of that working period. The hospital imposes two constraints:
The director of the hospital want to know how many possible working plans satisfying above constraint?
The input consists of one line which contains 3 positive integers N, K1, K2 (N ≤ 1000, K1 <K2≤ 400)
The output consists of only one single integer M modulo 109+7 where M is the total working plans satisfying the above constraints.
6 2 3
4
There are 4 working plans described as follows
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|}
\hline
working plan 1 & on & on & off & on & on & on\\
\hline
working plan 2 & on & on & off & on & on & off\\
\hline
working plan 3 & off & on & on & off & on & on\\
\hline
working plan 4 & on & on & on & off & on & on\\
\hline
\end{tabular}
\end{center}