众所周知，在算法竞赛中，出题人对他出的题的难度往往存在错误的估计。比如出题人本想出个中等题，没想到却出成了简单题；本想出个自闭题，结果数据太水变成了签到题。因此，为了让一场比赛能有良好的体验，有一个靠谱的验题人是非常重要的。

CC出好题目后，便拿给小马哥看。不出所料，这些题目小马哥全都是看一眼就会做了。而且，小马哥觉得这些题对于参赛选手来说也太水了（5个签到题哦～）。为了避免发生全场十几个队AK这种紧急事态，小马哥决定把一道签到题改成简单题，于是便有了现在这个题目。

小马哥非常喜欢数论，尤其钟爱“最大公约数”（Greatest Common Divisor，简称GCD）这一概念，因此他打算出一道和GCD有关的题目。小马哥首先给出了含n个正整数的序列，然后让你考虑该序列的所有子区间的数对应的GCD值，也就是说考虑所有的值。显然，这样的值一共有个。一个中二出题人可能会让你求这数中第k大的数，但幸运的是，小马哥是个正经出题人，因此它只让你求这个数之和模的结果。

小马哥在此预祝大家AK～

第一行是一个整数，表示数的个数。

接下来一行给出n个整数，其中第i个整数满足。

输出一行一个整数，表示ans的值。

5
16 4 7 21 3

72