---

Problem 734

---

A bit of prime

The logical-OR of two bits is $0$ if both bits are $0$, otherwise it is $1$.
The bitwise-OR of two positive integers performs a logical OR operation on each pair of corresponding bits in the binary expansion of its inputs.

For example, the bitwise-OR of $10$ and $6$ is $14$ because $10={1010}_2$, $6={0110}_2$ and $14={1110}_2$.

Let $T(n,k)$ be the number of $k$-tuples $(x_1,x_2,\cdots ,x_k)$ such that

• every $x_i$ is a prime $\le n$
• the bitwise-OR of the tuple is a prime $\le n$

For example, $T(5,2)=5$. The five $2$-tuples are $(2,2)$, $(2,3)$, $(3,2)$, $(3,3)$ and $(5,5)$.

You are given $T(100,3)=3355$ and $T(1000,10)\equiv 2071632(\mathrm{mod}1000000007)$.

Find $T({10}^6,999983)$. Give your answer modulo $1000000007$.

---

质数与位运算

在数的二进制表示下，每一位数字称为一个比特。两个比特之间的逻辑或定义如下：若这两个比特均为$0$，则结果为$0$，否则结果为$1$。
两个正整数的按位或定义如下：将这两个正整数表示成二进制，并将对应位置的比特进行逻辑或运算。

例如，$10$和$6$的按位或结果为$14$，这是因为$10={1010}_2$，$6={0110}_2$，而$14={1110}_2$。

记$T(n,k)$为满足以下条件的$k$-元组$(x_1,x_2,\cdots ,x_k)$的数目：

• 每个$x_i$均为小于等于$n$的质数；
• 元组中所有数按位或的结果是一个小于等于$n$的质数。

例如，$T(5,2)=5$，这五个$2$-元组分别是$(2,2)$、$(2,3)$、$(3,2)$、$(3,3)$和$(5,5)$。

已知$T(100,3)=3355$，$T(1000,10)\equiv 2071632(\mathrm{mod}1000000007)$。

求$T({10}^6,999983)$，并将你的答案对$1000000007$取余。

---