CF258C Little Elephant and LCM

The Little Elephant loves the LCM (least common multiple) operation of a non-empty set of positive integers. The result of the LCM operation of $ k $ positive integers $ x_{1},x_{2},...,x_{k} $ is the minimum positive integer that is divisible by each of numbers $ x_{i} $ . Let's assume that there is a sequence of integers $ b_{1},b_{2},...,b_{n} $ . Let's denote their LCMs as $ lcm(b_{1},b_{2},...,b_{n}) $ and the maximum of them as $ max(b_{1},b_{2},...,b_{n}) $ . The Little Elephant considers a sequence $ b $ good, if $ lcm(b_{1},b_{2},...,b_{n})=max(b_{1},b_{2},...,b_{n}) $ . The Little Elephant has a sequence of integers $ a_{1},a_{2},...,a_{n} $ . Help him find the number of good sequences of integers $ b_{1},b_{2},...,b_{n} $ , such that for all $ i $ $ (1

The first line contains a single positive integer $ n $ $ (1

In the single line print a single integer — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .