카드
시간 제한4초메모리 제한512 MB
서로 다른 숫자 카드 n장이 주어질 때, 공집합이 아닌 부분집합을 임의 순서로 배열해 만들 수 있는 모든 수의 합을 중복 포함해 1e9+7로 나눈 나머지를 구한다.
문제
숫자가 적힌 카드 n장이 있습니다. 이 중 일부 또는 전부를 적당히 늘어놓아 숫자를 만든다고 합시다. 이때 만들 수 있는 모든 숫자의 합을 구하세요.
예를 들어 1과 2가 있으면 만들 수 있는 숫자는 1, 2, 12, 21의 4개이므로 모두 더한 값은 36입니다. 늘어놓은 결과 같은 숫자가 나오더라도 늘어놓는 방법이 다르면 각각 따로 더합니다. 예를 들어 1이라는 카드와 11이라는 카드가 있으면 늘어놓아 111이 되는 방법이 2가지지만 각각을 별개의 것으로 보아 더합니다. 카드 중에 앞에 0이 붙은 카드는 없으며, 앞에 0이 붙는 숫자는 만들 수 없습니다. 답을 1,000,000,007로 나눈 나머지를 출력하세요.
입력
입력은 다음과 같은 형식으로 주어집니다.
n
a1
a2
...
an
첫째 줄에는 카드의 개수 n (1 ≤ n ≤ 200)이, 다음 n개 줄에는 각 카드에 적힌 숫자 ai (0 ≤ ai < 10000)가 주어집니다. 또한 여러 카드에 같은 숫자가 적혀 있는 경우는 없습니다.
출력
만들 수 있는 모든 숫자의 합을 1,000,000,007로 나눈 나머지를 한 줄에 출력하세요.