바이트랜드 복권

바이트랜드 복권에서 진행하는 가장 인기 있는 게임 중 하나는 "거대한 혼합(Huge blend)"입니다. 규칙은 간단합니다. 통 안에는 정해진 개수의 공이 들어 있고, 각 공에는 자연수가 하나씩 적혀 있습니다. 한 번의 추첨에서는 공을 몇 개 고른 뒤, 고른 공에 적힌 수들을 모두 곱한 값이 당첨 번호가 됩니다. 이 당첨 번호를 맞힌 사람이 1등 상금을 받습니다.

추첨 전에 통 안의 공의 개수와 각 공에 적힌 수는 모두 알려져 있습니다. 다만 공을 몇 개나 고를지는 알 수 없습니다. 전부 고를 수도 있고 단 한 개만 고를 수도 있습니다(적어도 한 개는 반드시 고릅니다).

바이트가이(ByteGuy)는 오랫동안 "거대한 혼합"에 당첨되기를 바랐습니다. 여러 번 실패한 끝에 자신의 당첨 확률이 궁금해진 그는 $n$, 즉 가능한 모든 추첨(공을 고르는 모든 공집합이 아닌 부분집합)에 대한 당첨 번호의 합을 계산하기로 했습니다. 그러나 계산 도중 컴퓨터가 과열되어 멈추는 바람에, 그는 더 간단한 값 $F(n)$을 구해 달라고 부탁했습니다. 여기서 $F$는 다음과 같이 정의됩니다.

• $k \le 9$이면 $F(k) = k$
• $k \ge 10$이면 $F(k) = F(s)$이며, $s$는 $k$의 각 자리 숫자를 모두 더한 값입니다.

예를 들어 $F(9) = 9$, $F(123) = 6$, $F(9876) = F(30) = 3$입니다.

공의 개수 $l$과 각 공에 적힌 수 $w_1, w_2, \dots, w_l$을 읽어들여, 공집합이 아닌 모든 부분집합에 대한 곱의 합 $n$에 대해 $F(n)$을 출력하는 프로그램을 작성하세요.

첫째 줄에 공의 개수를 나타내는 자연수 $l$이 주어집니다 ($1 \le l \le 10^6$). 둘째 줄에는 각 공에 적힌 자연수 $w_m$이 공백 하나로 구분되어 주어집니다 ($0 \le w_m \le 10^8$).

$F(n)$의 값을 정수 하나로 출력합니다.