CF594D REQ
Description
Today on a math lesson the teacher told Vovochka that the Euler function of a positive integer $ φ(n) $ is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. The number $ 1 $ is coprime to all the positive integers and $ φ(1)=1 $ .
Now the teacher gave Vovochka an array of $ n $ positive integers $ a_{1},a_{2},...,a_{n} $ and a task to process $ q $ queries $ l_{i} $ $ r_{i} $ — to calculate and print  modulo $ 10^{9}+7 $ . As it is too hard for a second grade school student, you've decided to help Vovochka.
Input Format
N/A
Output Format
N/A
Explanation/Hint
In the second sample the values are calculated like that:
- $ φ(13·52·6)=φ(4056)=1248 $
- $ φ(52·6·10·1)=φ(3120)=768 $
- $ φ(24·63·13·52·6·10·1)=φ(61326720)=12939264 $
- $ φ(63·13·52)=φ(42588)=11232 $
- $ φ(13·52·6·10)=φ(40560)=9984 $
- $ φ(63·13·52·6·10)=φ(2555280)=539136 $