gcd (gcd)

题目描述

小 Z 作为 ACM 实验室的老大，管理着 $n$ 名选手。小 Z 命令他们站成一排，从左到右第 $i$ 个选手的能力值为 $a_i$。

现在小 Z 决定派出至少一支队伍参加区域赛，每支队伍须是一个连续的非空区间。每个选手最多只能在一支队伍，相邻的两个选手可以在不同队伍中。

根据经验，一个队伍的能力值为这个队伍中所有选手能力值的最大公约数。同时小 Z 喜欢整齐的队伍，因此他选出的所有队伍的能力值必须相等。

现在小 Z 已经统计出了所有合法的方案。现在他需要去统计对于每名选手，有多少种方案使得该选手出现在一支队伍中。

输入格式

在文件 gcd.in 中读入。 第一行一个整数 $n$，表示选手数量。 第二行 $n$ 个整数 $a_{1},a_{2},\dots,a_{n}$，表示 $n$ 名选手的能力值。

输出格式

在文件 gcd.out 中输出。 输出一行 $n$ 个整数，第 $i$ 个数表示有几种方案使得第 $i$ 名选手在一支队伍中。由于答案很大，对 $10^9+7$ 取模。

样例

样例输入 #1

5
2 6 4 1 2

样例输出 #1

10 13 13 8 10

样例 1 解释：