시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)113655787.692%

문제

당신은 숫자 $k$를 싫어한다. 그래서 수를 쓸 때, 숫자 $k$는 쓰지 않으려 한다.

$f(x)$를, $x$의 10진법 표현에서 숫자 $k$를 모두 지운 수로 정의하자. 만일 $x$의 10진법 표현이 숫자 $k$로만 이루어져 있다면 $f(x)$를 $0$으로 정의한다.

예를 들어, $k = 3$일 때 $f(3135) = 15$, $f(2345) = 245$, $f(8185) = 8185$, $f(333333) = 0$이다.

숫자 $k$와 수 $N$이 주어질 때, $f(1) + f(2) + ... + f(N)$을 $1\,000\,000\,007$로 나눈 나머지를 구하여라.

입력

첫째 줄에 숫자 $k$가 주어진다.

둘째 줄에 수 $N$이 주어진다.

출력

첫째 줄에 $f(1) + f(2) + ... + f(N)$을 $1\,000\,000\,007$로 나눈 나머지를 출력하라.

제한

  • $1 \le k \le 9$
  • $1 \le N < 10^{100\,000}$
  • 입력으로 주어지는 수는 모두 정수다.

서브태스크

번호배점제한
18

$1 \le N < 1\,000\,000$.

217

$k = 1$, 어떤 $t$ ($0 \le t < 100\,000$)에 대해 $N = 10^t$.

311

$k = 1$.

423

$N < 10^{2\,000}$.

541

추가 제약 조건 없음.

예제 입력 1

3
5

예제 출력 1

12

$f(3) = 0$이고, $f(1) = 1$, $f(2) = 2$, $f(4) = 4$, $f(5) = 5$이므로, 답은 $1 + 2 + 0 + 4 + 5 = 12$가 된다.

예제 입력 2

3
4860000

예제 출력 2

465808830

출처

Contest > LG Collegiate Programming Contest > LGCPC 2025 예선 B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.