题号：NC310358
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
智乃定义一个十进制正整数是“好”的，当且仅当其十进制表示中
仅包含数字
和
，且数字
的出现次数
不超过 
。其十进制表示对应的字符串是其二进制表示对应的字符串的一个
后缀。
例如：
（10进制），其中只有
个数位为
，转写成二进制为
（2进制），其二进制包含后缀
，就说它是“好”的。
前
个“好”数分别为：
、
、
、
、
、
、
、
、
。
现在智乃想要知道，从小到大排列后的第
个符合条件的“好”数是多少。由于答案可能很大，请将答案对
)
取模后输出。
【名词解释】
字符串的
后缀：从字符串的最后一个字符开始，向前连续取若干个字符得到的字符串。更具体地，字符串
后
个字符构成的字符串被称为
的第
个后缀，也记为
![s[n-i+1..n]](https://www.nowcoder.com/equation?tex=s%5Bn-i%2B1..n%5D)
。
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数 )
代表数据组数，每组测试数据描述如下：
输入一个正整数 )
，表示要查询的第 
个“好”数。
输出描述:
对于每一组测试数据，新起一行输出一个整数，表示答案对 )
取模后的结果。