package main

import (
	"bufio"
	"fmt"
	"io"
	"math/bits"
	"os"
	"sort"
)

const MOD uint32 = 1000000007

type Num struct {
	off  int
	hi   int
	mod  uint32
	top1 uint64
	top2 uint64
}

type Node struct {
	i   int
	j   int
	num Num
}

type Heap struct {
	a    []Node
	pool []uint64
}

func lessNode(x, y Node, pool []uint64) bool {
	a, b := x.num, y.num
	if a.hi != b.hi {
		return a.hi < b.hi
	}
	if a.top1 != b.top1 {
		return a.top1 < b.top1
	}
	if a.top2 != b.top2 {
		return a.top2 < b.top2
	}
	for k := a.hi - 2; k >= 0; k-- {
		av := pool[a.off+k]
		bv := pool[b.off+k]
		if av != bv {
			return av < bv
		}
	}
	if x.i != y.i {
		return x.i < y.i
	}
	return x.j < y.j
}

func (h *Heap) push(x Node) {
	h.a = append(h.a, x)
	i := len(h.a) - 1
	for i > 0 {
		p := (i - 1) >> 1
		if !lessNode(h.a[i], h.a[p], h.pool) {
			break
		}
		h.a[i], h.a[p] = h.a[p], h.a[i]
		i = p
	}
}

func (h *Heap) pop() Node {
	n := len(h.a) - 1
	res := h.a[0]
	last := h.a[n]
	h.a = h.a[:n]
	if n == 0 {
		return res
	}
	h.a[0] = last
	i := 0
	for {
		l := i*2 + 1
		if l >= n {
			break
		}
		r := l + 1
		m := l
		if r < n && lessNode(h.a[r], h.a[l], h.pool) {
			m = r
		}
		if !lessNode(h.a[m], h.a[i], h.pool) {
			break
		}
		h.a[i], h.a[m] = h.a[m], h.a[i]
		i = m
	}
	return res
}

func addNums(dstOff int, a, b Num, src, dst []uint64) Num {
	maxHi := a.hi
	if b.hi > maxHi {
		maxHi = b.hi
	}
	baseA := a.off
	baseB := b.off
	baseD := dstOff
	carry := uint64(0)
	for i := 0; i <= maxHi; i++ {
		s, c := bits.Add64(src[baseA+i], src[baseB+i], carry)
		dst[baseD+i] = s
		carry = c
	}
	hi := maxHi
	if carry != 0 {
		hi++
		dst[baseD+hi] = carry
	}
	if maxHi < 0 && carry == 0 {
		hi = -1
	}
	var top1, top2 uint64
	if hi >= 0 {
		top1 = dst[baseD+hi]
		if hi > 0 {
			top2 = dst[baseD+hi-1]
		}
	}
	m := a.mod + b.mod
	if m >= MOD {
		m -= MOD
	}
	return Num{off: dstOff, hi: hi, mod: m, top1: top1, top2: top2}
}

func nextInt(data []byte, idx *int) int {
	n := len(data)
	for *idx < n && data[*idx] <= ' ' {
		*idx++
	}
	sign := 1
	if *idx < n && data[*idx] == '-' {
		sign = -1
		*idx++
	}
	val := 0
	for *idx < n && data[*idx] > ' ' {
		val = val*10 + int(data[*idx]-'0')
		*idx++
	}
	return val * sign
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	n := nextInt(data, &idx)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = nextInt(data, &idx)
	}
	sort.Ints(arr)

	L := (n+31+63)/64 + 1
	totalWords := 2 * n * L
	bufA := make([]uint64, totalWords)
	bufB := make([]uint64, totalWords)
	zeros := make([]uint64, totalWords)

	cur := make([]Num, n)
	for i, v := range arr {
		off := i * L
		hi := -1
		var top1 uint64
		if v != 0 {
			bufA[off] = uint64(v)
			hi = 0
			top1 = uint64(v)
		}
		cur[i] = Num{
			off:  off,
			hi:   hi,
			mod:  uint32(v % int(MOD)),
			top1: top1,
			top2: 0,
		}
	}

	src := bufA
	dst := bufB

	for m := n; m > 1; m-- {
		limit := 2 * m * L
		copy(dst[:limit], zeros[:limit])

		h := Heap{
			a:    make([]Node, 0, m-1),
			pool: dst,
		}

		ptr := 0
		for i := 0; i < m-1; i++ {
			off := ptr * L
			num := addNums(off, cur[i], cur[i+1], src, dst)
			ptr++
			h.push(Node{i: i, j: i + 1, num: num})
		}

		next := make([]Num, m-1)
		for t := 0; t < m-1; t++ {
			x := h.pop()
			next[t] = x.num
			if x.j+1 < m {
				off := ptr * L
				num := addNums(off, cur[x.i], cur[x.j+1], src, dst)
				ptr++
				h.push(Node{i: x.i, j: x.j + 1, num: num})
			}
		}

		cur = next
		src, dst = dst, src
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprintln(out, cur[0].mod)
	out.Flush()
}