---

Problem 643

---

$2$-Friendly

Two positive integers $a$ and $b$ are $2$-friendly when $\text{gcd}(a,b)=2^t,t>0$. For example, $24$ and $40$ are $2$-friendly because $\text{gcd}(24,40)=8=2^3$ while $24$ and $36$ are not because $\text{gcd}(24,36)=12=2^2\cdot 3$ not a power of $2$.

Let $f(n)$ be the number of pairs, $(p,q)$, of positive integers with $1\le p<q\le n$ such that $p$ and $q$ are $2$-friendly. You are given $f({10}^2)=1031$ and $f({10}^6)=321418433$ modulo $1000000007$.

Find $f({10}^{11})$ modulo $1000000007$.

---

$2$-友善数

如果正整数$a$和$b$满足$\text{gcd}(a,b)=2^t,t>0$，则称它们互为2-友善数。例如，$24$和$40$互为$2$-友善数，因为$\text{gcd}(24,40)=8=2^3$；而$24$和$36$则不是，因为$\text{gcd}(24,36)=12=2^2\cdot 3$不是$2$的幂。

考虑所有满足$1\le p<q\le n$且$p$和$q$互为$2$-友善数的正整数对$(p,q)$，并记这些数对的数目为$f(n)$。已知$f({10}^2)=1031$，$f({10}^6)$对$1000000007$取余的结果为$321418433$
.

Find $f({10}^{11})$并对$1000000007$取余。

---