← 返回比赛

已结束 COCR 入门赛#1

← 上一题下一题 →

A4714 | $计数改良$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

时间限制：1000ms，内存限制：512MB 某天，AC狗看到某位老师用暴力循环的办法做 $753$ 数的题目，非常惊讶，于是想到能不能不用循环来解？现在他把这个问题抛给了你。 你知道 $753$ 数是什么吗？在十进制表示中，数字 $7,5,3$ 至少出现一次，而其他数字从不出现的数就是 $753$ 数。 现在，你和老师要开始程序PK了。AC狗提出了 $T$ 组数据，让你们分别解决这道计数问题，看看谁用时少。

输入格式

输入由 $T + 1$ 行数据组成： 第一行一个整数 $T$ 表示询问的次数； 接下来 $T$ 行，每行一个正整数 $n$，求 $n$ 位的 $753$ 数的个数（答案需要对 $10 ^ 9 + 7$ 取模）。

输出格式

对于每个输入样例 $n$ ，都输出其答案（$n$ 位 $753$ 数的个数）。

输入输出样例

输入 #1

1
3

输出 #1

【数据范围】 对于 $100\%$ 的数据，保证 $1\leq T \leq 10^5$ 测试点$T$$n$$1,3$$=20$$\le15$$2,4$$=10^5$$\le 15$$5,6$$=10^5$$\le10^3$$7,8,9,10$$=10^5$$\le10^7$$11,12$$=10^5$$\le10^{18}$ 【样例解释】 样例组 #1：$3$ 位 $753$ 数共有 $6$ 个，分别是 $357,375,537,573,735,753$ 。

C++ 编辑器

输入

输出