题目描述
没错又是大家熟悉的斐波那契数列~
什么你不知道? 没关系我们来给你定义:
$F_1=1, F_2=1, F_i=F_{i-1}+F_{i-2}(i>2)$
然后你需要求出 $ \sum_{i=l}^{r} F_i$ 的值, $l,r$ 会由题目给出
由于答案可能很大, 你只需答案输出对1000000009取膜的结果即可~
输入描述
第一行一个整数T表示询问次数
接下来T行每行两个整数 $l,r$ 表示询问 $ \sum_{i=l}^{r} F_i$ 的值
输出描述
共T行, 每行一个整数表示对应的询问的答案
样例输入
3 1 2 3 5 233 456
样例输出
2 10 623800639
样例描述
斐波那契数列前5项的值分别为{1,1,2,3,5}
数据范围
$ 0 < T <= 2 * 10^{6} $
$ 1 <= l <= r < 10^{100000} $
保证输入文件在80MB内
子任务1:(20分)
$ T <=100, 1 <= l, r <=10^3 $
子任务2:(30分)
$ T <= 10^{5}, 1 <= l, r <= 10^6 $
子任务3:(50分)
$ T <= 100, 1 <= l, r <= 2 * 10^9 $
子任务4:(100分)
$ T <= 10^{5}, 1 <= l, r <= 2 * 10^{18} $
子任务5:(100分)
$ 0 < T <= 5 * 10^{5} $
子任务6:(100分)
$ 0 < T <= 10^{6} $
子任务7:(100分)
$ 0 < T <= 1500000 $
子任务8:(100分)
$ 0 < T <= 2 * 10^{6} $
