题目描述

你的女朋友是一位笨笨的魔法少女，但是，庆幸的是，你是一位魔法书的大收藏家，你有1e9+10本绝版的魔法书。

马上要开始魔法少女之间的排位赛了，你的女朋友只想带一本魔法书参赛，而她不知道带哪一本。此时，你想起来，你可以帮她设计一个程序，给定 n 个正整数 a，计算出这些数的乘积的约数之和，其值对 1e9+10 取模，最终结果便是要让她带第几本书。

当你熟练地写完万能头之后，你发现，这一切都是梦境，请在梦境结束之前，告诉你梦里的女朋友要带第几本书。

输入格式

1≤n≤100, 1≤a≤2e9

输出格式

答案需对 1e9+10 取模。

样例

3 
2 
6 
8

252

提示

by 陈代睿