Dabba loves Maths and his girlfriend Dhakan, so he either spends his day with dhakan or does maths all day. But he hates spending two consecutive days with dhakan (because she is a dhakan). He wants to make his schedule for his summer vacation as a sequence of doing maths or spending day with dhakan.

No of days of his summer vacation can vary from $l$ to $r$. You need to count in how many ways Dabba can select $k$ different schedule of the same number of days for his summer vacations, whose days can vary from $l$ to $r$.

For example if $k=2$, $l=1$ and $r=2$, if we define Maths day as {1} and Dhakan's day as {0}, here are all possible combination: {0}, {1}, {00}, {01}, {10}, {11}. But '00' can not be selected because it has $2$ consecutive Dhakan's day in a row. Now, we need to count in how many ways we can select $k = 2$ schedule of the same length in range $[1,2]$. Here they are: for no. of days=1 {0,1}; no. of days=2 {01,10}; {01,11}; {10,11}. so answer for $k$=2,$l$=1 and $r$=2 will be 4.

He wants you to tell him in how many ways can do that, modulo $1000000007$ for $k=200$, $l=1$ and $r=10^{18}$.