A - Simple Math 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

正整数 N, M が与えられます。\lfloor \frac{10^N}{M} \rfloor を M で割った余りを求めてください。

\lfloor x \rfloor について \lfloor x \rfloor は、 x を超えない最大の整数を表します。例としては次のようになります。
  • \lfloor 2.5 \rfloor = 2
  • \lfloor 3 \rfloor = 3
  • \lfloor 9.9999999 \rfloor = 9
  • \lfloor \frac{100}{3} \rfloor = \lfloor 33.33... \rfloor = 33

制約

  • 1 \leq N \leq 10^{18}
  • 1 \leq M \leq 10000

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

答えを出力せよ。

入力例 1

1 2

出力例 1

1

\lfloor \frac{10^1}{2} \rfloor = 5 なので、5 を 2 で割った余りの 1 を出力します。

入力例 2

2 7

出力例 2

0

入力例 3

1000000000000000000 9997

出力例 3

9015

Score : 300 points

Problem Statement

Given positive integers N and M, find the remainder when \lfloor \frac{10^N}{M} \rfloor is divided by M.

What is \lfloor x \rfloor? \lfloor x \rfloor denotes the greatest integer not exceeding x. For example:
  • \lfloor 2.5 \rfloor = 2
  • \lfloor 3 \rfloor = 3
  • \lfloor 9.9999999 \rfloor = 9
  • \lfloor \frac{100}{3} \rfloor = \lfloor 33.33... \rfloor = 33

Constraints

  • 1 \leq N \leq 10^{18}
  • 1 \leq M \leq 10000

Input

Input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

1 2

Sample Output 1

1

We have \lfloor \frac{10^1}{2} \rfloor = 5, so we should print the remainder when 5 is divided by 2, that is, 1.

Sample Input 2

2 7

Sample Output 2

0

Sample Input 3

1000000000000000000 9997

Sample Output 3

9015