Fibonacci Product Sum

Given three integers \(k\), \(m\), and \(n\), compute the following sum modulo \(10^9+7\):

\[ S = \sum_{i=m}^{n} \prod_{j=i}^{i+k-1} a_j \]

Here, \(\{a\}\) represents the Fibonacci sequence defined as \(a_1 = 1\), \(a_2 = 1\) and \(a_i = a_{i-1} + a_{i-2}\) for \(i \ge 3\). The answer should be given modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three space-separated integers \(k\), \(m\), and \(n\).

outputFormat

Output a single integer which is the value of \(S\) modulo \(10^9+7\).

sample

1 1 5

12