module mod_generate_fn
    private
type term
    integer(4):: factor,multiplier
end type
type factorized_num
    type(term), pointer:: num(:)
end type

public factorized_num, generate_fn, init_fn, calc_ldb, div_fn, print_fn, multipl_fn
contains
subroutine generate_fn(x, fx)
    integer(4):: x, now_x
    type(factorized_num):: fx
    integer(4):: i

    now_x = x
    do i=2, nint(sqrt(real(x)))
        do while (mod(now_x, i) == 0)
            call add_factor_to_fn(fx, i)
            now_x = now_x / i
        end do
    end do

    if (now_x /= 1)then
        call add_factor_to_fn(fx, now_x)
    end if
    ! call print_fn(fx, 'pm')
end subroutine


subroutine init_fn(fx)
    type(factorized_num):: fx
    allocate(fx%num(0))
end subroutine


subroutine add_factor_to_fn(fx,pn)
    type(factorized_num):: fx, tmp
    integer(4):: now_size
    integer(4):: pn, i

    now_size = size(fx%num(:))
    do i=1, size(fx%num(:))
        if (fx%num(i)%factor == pn) then
            fx%num(i)%multiplier = fx%num(i)%multiplier + 1
            return
        end if
    end do
    ! not found num in fx%num(:)%factor--------------------
    call append_fn(fx, pn, 1)
end subroutine


subroutine print_fn(fn, word)
    type(factorized_num):: fn
    integer:: i
    character(*):: word

    print"(a5' : ----------------')", word
    do i = 1, size(fn%num(:))
        print"(i7' * 'i7)", fn%num(i)%factor, fn%num(i)%multiplier
    end do
end subroutine


subroutine calc_ldb(fldb, fn)
    type(factorized_num):: fldb, fn
    integer(4):: i,j
    integer(4):: fac, mul
    logical:: fac_exist
    
    do i=1,size(fn%num(:))
        fac = fn%num(i)%factor
        mul = fn%num(i)%multiplier
        fac_exist = .false.
        
        do j=1, size(fldb%num(:))
            if (fldb%num(j)%factor == fac)then
                fldb%num(j)%multiplier = max(fldb%num(j)%multiplier,mul)
                fac_exist = .true.
                exit
            end if
        end do

        if (.not. fac_exist) then
            call append_fn(fldb,fac,mul)
        end if
    end do
end subroutine

function div_fn(a, ldb, mod_) result(ret)
    integer(4):: a, mod_
    integer(8):: ldb, ret, a_inv
    a_inv = calc_inv(a, mod_)
    ! print*, 'ainv', a_inv
    ret = mod(a_inv*ldb, mod_)
    ! print*, 'ret', ret

end function

function calc_inv(a, mod_) result(ret)
    integer(4):: a, mod_
    integer(8):: ret, a8, n, m8
    m8 = mod_
    n = mod_-2
    ret = 1
    a8 = int8(a)
    do while(n>0)
        if (mod(n,2)/=0) ret = mod(int8(ret*a8), m8)
        n = n / 2
        a8 = mod(int8(a8*a8), m8)
    end do
end function


function multipl_fn(fn, mod_) result(ret)
    type(factorized_num):: fn
    integer(4):: mod_, i, fac, mul
    integer(8):: ret
    ret = 1
    do i=1, size(fn%num(:))
        fac = fn%num(i)%factor
        mul = fn%num(i)%multiplier
        ret = mod(ret*mod(fac**mul, mod_), mod_)
    end do
end function

subroutine append_fn(fx, fac, mul)
    type(factorized_num):: fx,tmp
    integer(4):: now_size, fac, mul

    now_size = size(fx%num(:))
    allocate(tmp%num(now_size))
    tmp%num(:) = fx%num(:)
    deallocate(fx%num)
    allocate(fx%num(now_size+1))
    fx%num(:now_size) = tmp%num(:)
    deallocate(tmp%num)
    fx%num(now_size+1)%factor = fac
    fx%num(now_size+1)%multiplier = mul
end subroutine

end module

program flatten
    use mod_generate_fn
    implicit none
    integer(4):: n, i
    integer(4), allocatable:: a(:)
    integer(4), parameter:: mod_ = 1000000007
    integer(8) :: sumb, ldb, b
    type(factorized_num), allocatable:: fa(:)
    type(factorized_num):: fldb

    read*, n
    allocate(a(n), fa(n))
    ! read*, a(:)
    a(:) = [(i*100, i=1, n)]

    call init_fn(fldb)
    do i = 1,n
        call init_fn(fa(i))
    end do
    do i=1,n
        call generate_fn(a(i), fa(i))
    end do

    do i=1,n
        call calc_ldb(fldb,fa(i))
    end do
    ! call print_fn(fldb,'ldb')
    ldb = multipl_fn(fldb, mod_)
    ! print*, 'ldb', ldb

    sumb = 0
    do i = 1,n
        b = div_fn(a(i), ldb, mod_)
        sumb = mod(sumb+b, mod_)
    end do

    print*, sumb
end program flatten