11537: 【原1537】Ficos的坚持
题目
题目描述
author: CodeVS,greatwall1995 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1537
Description
筛选出了所有有效的字符串，Ficos又陷入了思考：每一个数字背后的含义是什么？在焦头烂额之际，Ficos看到Livia的博客上更新了两篇文章，分别是对L数和 \(Z_q\)集合的研究。
\(L\)数是一个十进制数，其定义如下：
- “1”是一个\(L\)数。
- 一个以“1”结尾的\(L\)数在末尾加上“0”或“1”都是\(L\)数。
- 一个以“0”结尾的\(L\)数在末尾加上“0”是\(L\)数。
\(Z_q\)集合是所有\(q\)的倍数构成的集合，即如果一个数\(k\)能被\(q\)整除，当且仅当它是\(Z_q\)集合的一个元素。
思索片刻后，Ficos想到每一个有效数码串对应了一个\(q\)，它的含义即是\(Z_q\)集合中最小的\(L\)数。这些有效字符串最终会转化为一个01串，根据这个01串或许可以直接翻译出约会的时间地点。
现在Ficos希望你能帮助它把每一个\(q\)转化成相应的在\(Z_q\)集合中最小的\(L\)数。
Input Format
一个数\(q\)。
Output Format
输出\(Z_q\)集合中最小的\(L\)数，考虑到这个数字可能很大，所以请输出答案除以\(10^7+9\)所得到的余数。
如果不存在这样的数，请输出“Impossible”！
Sample Input
6
Sample Output
1110
Limits
对于30%的数据，答案不超过\(10^6\)，或不存在这样的数;
对于60%的数据，答案不超过\(10^{20}\)，或不存在这样的数;
对于100%的数据，\(1 \leq q \leq 10^7\);
Hint
其实这题的数据规模可以出到\(10^{18}\)，有兴趣的同学可以想一想。
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！