問題文

整数 $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