---

Problem 508

---

Integers in base i-1

Consider the Gaussian integer i-1. A base i-1 representation of a Gaussian integer a+bi is a finite sequence of digits d_n-1d_n-2…d₁d₀ such that:

• a+bi = d_n-1(i-1)^n-1 + d_n-2(i-1)^n-2 + … + d₁(i-1) + d₀
• Each d_k is in {0,1}
• There are no leading zeroes, i.e. d_n-1 ≠ 0, unless a+bi is itself 0

Here are base i-1 representations of a few Gaussian integers:

11+24i → 111010110001101
24-11i → 110010110011
8+0i → 111000000
-5+0i → 11001101
0+0i → 0

Remarkably, every Gaussian integer has a unique base i-1 representation!

Define f(a+bi) as the number of 1s in the unique base i-1 representation of a+bi. For example, f(11+24i) = 9 and f(24-11i) = 7.

Define B(L) as the sum of f(a+bi) for all integers a, b such that |a| ≤ L and |b| ≤ L. For example, B(500) = 10795060.

Find B(10¹⁵) mod 1 000 000 007.

---

i-1进制的整数

考虑高斯整数i-1，我们定义任意高斯整数a+bi的i-1进制表示为一个有限的数字序列d_n-1d_n-2…d₁d₀满足：

• a+bi = d_n-1(i-1)^n-1 + d_n-2(i-1)^n-2 + … + d₁(i-1) + d₀
• 每个d_k都在集合{0,1}中
• 没有前导零，也就是说，除非a+bi本身为0，否则d_n-1 ≠ 0

以下是一些高斯整数的i-1进制表示：

11+24i → 111010110001101
24-11i → 110010110011
8+0i → 111000000
-5+0i → 11001101
0+0i → 0

值得注意的是，每个高斯整数都有唯一的i-1进制表示！

定义f(a+bi)为高斯整数a+bi的i-1进制表示中1的个数。例如，f(11+24i) = 9，以及f(24-11i) = 7。

对于所有满足|a| ≤ L和|b| ≤ L的整数a和b，定义B(L)为所有f(a+bi)的和。例如，B(500) = 10795060。

求B(10¹⁵) mod 1 000 000 007。

---