#P18527. Count off 3
Count off 3
Count off 3
小 Z 和小 R 又开始玩报数游戏。这次,由于小 R 出国交流,他们只能在线交流。计算机用二进制表示数据,这让他们想到把原来十进制的游戏改到二进制。
传统的报数游戏要跳过 7 的倍数或者包含数字 7 的数;但二进制没有数字 7,而是否为 7 的倍数与表示进制无关,因此这种改法并不有趣。不过,同一串数字在不同进制下会表示不同的值,例如 1010 在二进制下是 10,在三进制下是 30。他们于是提出:只允许报出在任何进制下都不是 7 的倍数的数字串。
正式定义如下:非空字符串 若只含字符 0、1 且首字符不是 0,称为一个合法 01 串。
对合法 01 串 和整数 ,定义将 视为 进制时的值为 。若串长为 ,下标从 0 开始,则
其中字符 按对应数值 0 或 1 计算, 是最高位, 是最低位。
给你一个合法 01 串 作为报数上界。求满足以下条件的合法 01 串 的数量:
- ,即不超过上界的含义按二进制数值判断。
- 对每一个整数 ,7 都不整除 。
答案对 取模。
输入格式
第一行包含整数 (),表示测试用例数。
每个测试用例占一行,包含一个合法 01 串 (),表示上界。每个串分别满足该长度限制,原题没有额外的所有串长度之和限制。
输出格式
每个测试用例输出一行一个整数,表示所求数量对 取模的结果。
完整原样例
5
1
1010
110101
1000111000
101101001000
1
2
15
114
514