AT_dwango2017final_b ニワンゴくんの約数

[problemUrl]: https://atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_b ニワンゴくんは、正の整数からなる数列 $ x_1,\ x_2,\ ...,\ x_N $ を持っています。次の $ Q $ 個のクエリに順に答えてください。 - クエリ: $ 1\ ≦\ l_i\ ≦\ r_i\ ≦\ N $ が与えられるので、$ x_{l_i},\ x_{l_i+1},\ ...,\ x_{r_i} $ の積 $ x_{l_i}x_{l_i+1}...x_{r_i} $ の約数の個数を $ 10^9\ +\ 7 $ で割ったあまりを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ x_1 $ $ : $ $ x_N $ $ l_1 $ $ r_1 $ $ : $ $ l_Q $ $ r_Q $

クエリ毎に、整数 $ x_{l_i}x_{l_i+1}...x_{r_i} $ の約数の個数を $ 10^9\ +\ 7 $ で割ったあまりを一行に出力せよ。

### 制約 - $ 1\ ≦\ N,\ Q\ ≦\ 10^5 $ - $ 1\ ≦\ x_i\ ≦\ 10^5\ (1\ ≦\ i\ ≦\ N) $ - $ 1\ ≦\ l_i\ ≦\ r_i\ ≦\ N\ (1\ ≦\ i\ ≦\ Q) $ - 入力はすべて整数である。 ### Sample Explanation 1 最初のクエリにおいて、$ x_1x_2x_3x_4x_5x_6=64800 $ の約数の個数は $ 90 $ 個なので、$ 90 $ を出力します。