简单数学题

简单数学题

题号：NC22572
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

定义如下函数:

$\ f(x)= \begin{cases} 1 & {x=1}\\ \max\{ t\ |\ {x \bmod t = 0}\ \&\&\ |\mu(t)| = 1 \}& {x \geq 2} \end{cases}$

其中 $\mu(t)$ 为莫比乌斯函数，详见：https://en.wikipedia.org/wiki/M%C3%B6bius_function

对于任何整数 $\ x$ ，若有 $x = p_{1}^{n_{1}}p_{2}^{n_{2}}...p_{k}^{n_{k}}$ ，其中 $p_{i}$ 是 $\ x$ 第 $\ i$ 大的质因子，则

$g(x) = p_{1}^{\beta(n_{1})}p_{2}^{\beta(n_{2})}...p_{k}^{\beta(n_{k})}$

$\beta(x)= \begin{cases} 0& \text{x is even}\\ 1& \text{x is odd} \end{cases}$

现在定义 $\ F(a, b, c) = g(f(a)*f(b)*f(c))$

并给出三个长度均为 $\ n$ 的数列

$\ A_{1}A_{2}A_{3}...A_{n}$

$\ B_{1}B_{2}B_{3}...B_{n}$

$\ C_{1}C_{2}C_{3}...C_{n}$

对于某个整数 $\ z$ ，如有

$\ z = F(A_{i}, B_{j}, C_{k})(1 \leq i,j,k \leq n)$

则称 $\ GF(i, j, k)$ 为z的一种表示

设 $\ S$ 集合为 $S = \{ z|z=F(A_{i}, B_{j}, C_{k}),1 \leq i,j,k \leq n \}$ ， $\ {|Z|}$ 为 $\ S$ 中元素的个数

求 $ans = \sum_{i=1}^{|Z|}{z_{i} k_{i}}$ ，其中 $z_{i}$ 是集合 $\ S$ 的第 $\ i$ 个元素，其中 $k_{i}$ 为 $z_{i}$ 的不同的表示的个数。答案对 $\ 10^{9}+7$ 取模。

注意：对于一个数 $\ z$ ，如果 $\ z = F(A_{i_{1}}, B_{j_{1}}, C_{k_{1}})) = F(A_{i_{2}}, B_{j_{2}}, C_{k_{2}}))$ ,

只要 $i_{1}\neq i_{2}\ or\ j_{1}\neq j_{2}\ or\ k_{1}\neq \ k_{2}$ ，那么我们说 $\ z$ 的这两种表示的两种不同的表示。

输入描述:

首先输入一个整数 $\ n (1 \leq n \leq 10^{5})$ ，接下来是三行整数。

第一行有 $\ n$ 个整数--- $\ A_{1}A_{2}A_{3}...A_{n} ( \ 1 \leq \ A_{1}A_{2}A_{3}...A_{n} \leq 10^{18} )$ 。

第二行有 $\ n$ 个整数--- $\ B_{1}B_{2}B_{3}...B_{n} ( \ 1 \leq \ B_{1}B_{2}B_{3}...B_{n} \leq 10^{18} )$ 。

第三行有 $\ n$ 个整数--- $\ C_{1}C_{2}C_{3}...C_{n} ( \ 1 \leq \ C_{1}C_{2}C_{3}...C_{n} \leq 10^{18} )$ 。

保证后三行输入的所有整数每个数的最大质因子不会超过 $\ 71$ 。

输出描述:

输出一个整数，即为上述所需要的答案。输出对取模。

示例1

输入

复制

输出

复制

说明

很容易推出

所以