---
# System prepended metadata

title: LOVELYPAIR

---

# LOVELYPAIR

## Tóm tắt đề
Đếm số lượng **cặp số đáng yêu** trong đoạn $[l,\ r]$ $(\text{mod}\ 10^9+7)$, biết rằng **cặp số đáng yêu** là các cặp số $(a, b)$ thỏa mãn $l \leq a < b \leq r$ và $(a \oplus b) \equiv (a \land b) \mod{k}$.

## Giới hạn
$1 \leq l < r \leq 10^{18};\ 1 \leq k \leq 10^4$

## Lời giải
Digit DP 5 trạng thái. Ta gọi hàm digit DP của mình là $\texttt{dp(pos, geqL, leqR, bound, diff_mod)}$ với
-    $\texttt{pos}$: Vị trí chữ số đang xét trong hệ nhị phân của 2 số $a,b$
-    $\texttt{geqL}$: $a > l$ hay chưa
-    $\texttt{leqR}$: $b < r$ hay chưa
-    $\texttt{bound}$: $a < b$ hay chưa
-    $\texttt{diff_mod}$: Chênh lệch số dư khi chia cho $k$ của $a$ và $b$ hiện tại.

Việc còn lại là tiến hành digit DP chuyển trạng thái và xét các trường hợp $0/1$ tương ứng của các cặp số $(a, b)$.