C. 数字【普及】

内存限制:256 MiB 时间限制:1000 ms 输入文件: digit.in 输出文件: digit.out
题目类型:传统 评测方式:文本比较

题目描述

你需要求出一个 n 位数 x ,满足以下两个条件:

  • x 各位数字之和除以 p 余数尽可能小。
  • 已经满足 1 的情况下, x 的值尽可能小。

各位数字之和:一个数的每个位置上的数字加起来的总和。例如, 123 的各位数字之和为 1+2+3=6

输入格式

输入共一行,两个整数 n,p

输出格式

输出一个整数,表示上述问题的答案。

样例

样例输入 #1

3 8

样例输出 #1

107

样例输入 #2

1 1

样例输出 #2

1

样例输入 #3

5 3

样例输出 #3

10002

样例输入 #4

2 7

样例输出 #4

16

样例解释 #1

三位数包含 100,101,\dots,999 。其中 107 的各位数字之和为 1+0+7=8 8 除以 8 的余数为 0

数据范围与提示

数据范围

对于 30\% 的数据, 1\le n\le 18 1\le p\le 200
对于 100\% 的数据, 1\le n \le 10^6 1 \le p \le 10^9