Yenə də Fibonacci ədədləri

Bildiyiniz kimi, Fibonacci ədədləri aşağıdakı kimi müəyyən edilir:

Verilən a və b üçün hesablayın.

Giriş məlumatları

Bir neçə testdən ibarətdir. Hər bir test ayrıca bir sətirdə yerləşir və burada iki qeyri-mənfi tam ədəd a və b (0 ≤ a ≤ b ≤ 10^9) verilir.

Çıxış məlumatları

Hər bir test üçün ayrıca bir sətirdə S mod 10^9 çıxarın, çünki S çox böyük ola bilər.

Nümunələr