CF1891D Suspicious logarithms

Let $ f $ ( $ x $ ) be the floor of the binary logarithm of $ x $ . In other words, $ f $ ( $ x $ ) is largest non-negative integer $ y $ , such that $ 2^y $ does not exceed $ x $ . Let $ g $ ( $ x $ ) be the floor of the logarithm of $ x $ with base $ f $ ( $ x $ ). In other words, $ g $ ( $ x $ ) is the largest non-negative integer $ z $ , such that $ {f(x)}^{z} $ does not exceed $ x $ . You are given $ q $ queries. The $ i $ -th query consists of two integers $ l_i $ and $ r_i $ . The answer to the query is the sum of $ g $ ( $ k $ ) across all integers $ k $ , such that $ l_i \leq k \leq r_i $ . Since the answers might be large, print them modulo $ {10^9 + 7} $ .

The first line contains a single integer $ q $ — the number of queries ( $ 1 \leq q \leq 10^5 $ ). The next $ q $ lines each contain two integers $ l_i $ and $ r_i $ — the bounds of the $ i $ -th query ( $ 4 \leq l_i \leq r_i \leq 10^{18} $ ).

For each query, output the answer to the query modulo $ 10^9 + 7 $ .

The table below contains the values of the functions $ f $ ( $ x $ ) and $ g $ ( $ x $ ) for all $ x $ such that $ 1 \leq x \leq 8 $ . $ x $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ $ 8 $ $ f $ $ 0 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $ $ 2 $ $ 2 $ $ 3 $ $ g $ $ - $ $ - $ $ - $ $ 2 $ $ 2 $ $ 2 $ $ 2 $ $ 1 $