C. 2021北京队选拔模拟赛1-C

你的公司有无限个妹子，她们要开演唱会，每个人有一个不同的迷之分数 a，a ∈ {1, 2, 3, 5, 7}，每种分 数的妹子也有无限个。你要选出n个妹子排成一排，这n个妹子的好感度定义为将a1,a2,...,an 连接起 来形成的正整数(ai 表示选择的 n 个人中第 i 个人的迷之分数)。而观众不喜欢好感度能整除 2,3,5,7,11,47 中任意一个数的妹子组合，你需要计算出你有多少种选择方案，两种选择方案视为不同当且仅当有一个位置的妹子的迷之分数不同。

一行一个正整数 n。

一行一个整数，表示答案，取模 9973。

【数据规模与约定】

• 对于 30% 的数据，n ≤ 1000
• 对于 60% 的数据，n ≤ 10000000
• 对于 100% 的数据，n ≤ 1000000000