P17571 「FAOI-R(-2)」数列计数 2024

**本题为[「FAOI-R2」A trip to Macao](https://www.luogu.com.cn/problem/P10036) 的加强版，曾被放入 OIFC 2024 NOIP 联考**。

给定正整数 $n$。对于一个长度为 $k$ 的**正整数**数列 $\{a\}$，称它是好的当且仅当： - $a_1 = 1$，$a_k=n$。 - 对于所有 $2\le i\le k$，$a_i \in [a_{i-1}+1,2a_{i-1}]$； 请你求出有多少好的正整数数列（此处数列的长度 $k$ 可以是任意正整数）。答案对 $10^9+7$ 取模。

**本题有多组测试数据**。 第一行一个正整数 $q$，代表数据组数。 接下来 $q$ 行，每行一个正整数 $n$。

输出 $q$ 行，每行一个非负整数表示答案。

**【数据范围】** 对于所有数据，均有 $1\le q \le 64$，$1 \le n \le 10^{18}$。 **本题采用捆绑测试**。 ::cute-table{tuack} |子任务编号|分数|$q=$|$n\le$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$1$|$5$|$1$|$10$|无 |$2$|$7$|$1$|$450$|无 |$3$|$10$|$1$|$5000$|无 |$4$|$8$|$1$|$10^6$|无 |$5$|$23$|$1$|$10^8$|无 |$6$|$3$|$16$|$10^8$|B| |$7$|$7$|$5$|$10^{18}$|A| |$8$|$25$|$1$|$10^{18}$|无 |$9$|$3$|$48$|$10^{18}$|B |$10$|$9$|$64$|$10^{18}$|无 特殊性质 A ：$n=2^x,x\in \mathbb{Z^{\text{*}}}$ 特殊性质 B ：输入的 $n$ **递增**。