D - 表現の自由 ( Freedom of expression ) Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

整数 N と M が与えられる時、整数 N を M 個の整数の積で表す方法は何通りあるでしょうか。
その答えを 1,000,000,007 で割った余りを答えてください。

入力

入力は以下の形式で標準入力から与えられる。 
N M
  • 入力は 1 行のみからなり、整数 N(1 ≦ |N| ≦ 10^9) と整数 M(1 ≦ M ≦ 10^5) が空白区切りで与えられる。

出力

整数 N を M 個の整数の積で表す方法の数を 1,000,000,007 で割った余りを標準出力に 1 行で出力せよ 。
なお、最後には改行を出力せよ。

入力例 1

10 2

出力例 1

8
  • 10 を 2 つの整数の積で表す方法は以下の 8 通りになります。
    • 1 \times 10
    • 2 \times 5
    • 5 \times 2
    • 10 \times 1
    • (-1) \times (-10)
    • (-2) \times (-5)
    • (-5) \times (-2)
    • (-10) \times (-1)

入力例 2

1000000000 1

出力例 2

1
  • 1,000,000,000 を 1 つの積で書き表すには 1,000,000,000 と書くしか無いので、1 通りになります。

入力例 3

-2 3

出力例 3

12
  • -2 を 3 つの整数の積で表す方法は以下の 12 通りになります。
    • 1 \times 1 \times (-2)
    • 1 \times 2 \times (-1)
    • 1 \times (-1) \times 2
    • 1 \times (-2) \times 1
    • 2 \times 1 \times (-1)
    • 2 \times (-1) \times 1
    • (-1) \times 1 \times 2
    • (-1) \times 2 \times 1
    • (-1) \times (-1) \times (-2)
    • (-1) \times (-2) \times (-1)
    • (-2) \times 1 \times 1
    • (-2) \times (-1) \times (-1)

入力例 4

50 1000

出力例 4

96554651

Source Name

ARC 004