짝수 홀수 반복 횟수의 합

시간 제한2초메모리 제한512 MB

요약

짝수는 2로 나누고 홀수는 1을 더해 1에 도달할 때까지 걸리는 단계 수를 f(X)라 할 때, [L, R] 구간 모든 X의 f(X) 합을 10^9+7로 나눈 나머지를 구한다. L과 R은 10^18까지 커질 수 있다.

난이도: 어려움10점 중 8점
유형: 수학, 비트 연산, 분할 정복, 동적 계획법
정답자: 아직 제출이 없습니다

문제

양의 정수 하나를 인자로 받아 정수를 돌려주는 함수 $f(X)$ 가 다음과 같이 정의되어 있다.

function f(X):
    iterations := 0
    while X is not 1:
        if X is even:
            divide X by 2
        else:
            add 1 to X
        add 1 to iterations
    return iterations

어떤 양의 정수 $X$ 를 넣어도 이 함수는 반드시 끝난다는 사실을 증명할 수 있다. 구간 $[L, R]$ 이 주어지면 다음 합을 구하라.

$S = f(L) + f(L + 1) + \cdots + f(R - 1) + f(R)$

입력

첫째 줄에 두 정수 $L$ 과 $R$ 이 주어진다. ( $1 \le L \le R \le 10^{18}$ )

출력

$S$ 를 소수 $10^9 + 7$ 로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
1 127
```
예상 출력
```
1083
```
예제 2
입력
```
74 74
```
예상 출력
```
11
```