12944: 雯神与狗不得不说的故事3

上回说到雯神现在不怕狗了反而喜欢狗了。今天雯神走到了一个奇怪的地方，这个地方有好多狗狗，并且有n种不同的狗狗，每只狗狗上有一个数字，雯神为了知道有多少只狗狗特地的数了一下，发现写着ai的狗狗有ai^mi只。但是实在太多了。雯神决定用一个数来表示这些狗狗，但是因为雯神数学没学好，所以连求LCM都不会，谁来帮帮雯神。其实是雯神觉得LCM太简单了，不想自己动手解决而以啦！！！ 

求 u =LCM( a[1] ^ m[1], a[2] ^ m[2], ... , a[n] ^ m[n] )%(10^9+7)。 

Ps: LCM 即（Least Common Multiple）

多组输入。

对于每组数据：

第一行一个n。( 2 <= n && n <= 10 )

下面一行n个数，依次表示 m[1], ... , m[n] ( m[i] >=1 && m[i] <= 1000 , i = 1...n )

再下一行n个数，表示a[1], ... , a[n] ( a[i] >= 1 && a[i] <= 100000, i = 1...n )

对于每组数据，输出一行，该行包含一个整数u%(10^9+7)的结果。

3
1 1 1
1 2 3

6