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 $\leq n$
the bitwise-OR of the tuple is a prime $\leq 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 \pmod{1\ 000\ 000\ 007}$.

Find $T(10^6,999983)$. Give your answer modulo $1\ 000\ 000\ 007$.

质数与位运算

在数的二进制表示下，每一位数字称为一个比特。两个比特之间的逻辑或定义如下：若这两个比特均为$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 \pmod{1\ 000\ 000\ 007}$。

求$T(10^6,999983)$，并将你的答案对$1\ 000\ 000\ 007$取余。