沿着河边看一看清冷的夏夜，耳机里是AR的《呼兰河传》。AR的呼兰河并非一条河，而是一个故乡小城的生活日记。静谧的童年，孩子看世界的眼光，花开鸟飞间的自由，塑造了一方那个时代中少有的美好。现在，你需要回答以下问题，才可倾听这首《呼兰河传》带来的温柔，试试吧。给你n个数，选择一些数，使得LCM最大，输出LCM的最大值并对1e9+9取模。
LCM：最小公倍数
输入描述:
第一行输入一个n，代表数字的个数。
第二行输入n个数a[i]，代表每个数的值。
1<=n<=1e6,1<=a[i]<=1e5。
输出描述:
选择一些数能得到的最大LCM，由于LCM太大了，你只需要对1e9+9取模即可。