#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = unsigned long long;
using ld = long double;
//ll MOD = 1'000'000'007;
ll MOD = 1'000'000'000;
//ll MOD = 1.8446744074E19;

map<ll, ll> dp;



ll solution(ll n){
    if(dp.find(n) != dp.end()) return dp[n];
    ll result;
    
    ll a, b;
    a = solution(n/2);
    b = solution(n/2+1+(-2 *!(n%2)));
    
    if(n%2) result = ((a * a)%MOD + (b * b)%MOD)%MOD;
    else result = ((((2*b)%MOD + a)%MOD)*a)%MOD;
    dp[n] = result;
    
    return result;
}




int main() {
    ll A, B;
    cin >> A >> B;
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    
    
    ll sumA = solution(A+1);
    ll sumB = solution(B+2);
    
    
    // 이게 F_n*F_(n+1)이여서
    
    // 아 생각해보니까 dp자체에서 mod를 쓰니까 더 작을 수 있구나..
    if(sumB < sumA) cout << (sumB - sumA + MOD) % MOD;
    else cout << (((sumB - sumA))%MOD);
    

    return 0;
}