/* 3828 */

 #include <iostream>

 #include <sstream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <bitset>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 #include <iterator>

 #include <iomanip>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>

 #define stpii            set<pair<int, int> >

 #define mpii            map<int,int>

 #define vi                vector<int>

 #define pii                pair<int,int>

 #define vpii            vector<pair<int,int> >

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define clr                clear

 #define pb                 push_back

 #define mp                 make_pair

 #define fir                first

 #define sec                second

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 #define lson            l, mid, rt<<1

 #define rson            mid+1, r, rt<<1|1

 const int INF = 0x3f3f3f3f;

 const int maxl = ;

 const int maxn = ;

 const int mod = ;

 __int64 a[maxn];

 char word[maxn][maxl];

 string sw[maxn];

 int nxt[maxl];

 int Len[maxn];

 bool visit[maxn];

 int dp[<<][];

 int M[][];

 int n;

 void f(char *s, __int64 x) {

     int l = ;

     while (x) {

         s[l] = (x & ) + '';

         ++l;

         x >>= ;

     }

     s[l] = '\0';

     reverse(s, s+l);

 }

 void getnext(char *s) {

     int i = , j = -;

     int l = strlen(s);

     nxt[] = -;

     while (i < l) {

         if (j==- || s[i]==s[j]) {

             ++i;

             ++j;

             nxt[i] = j;

         } else {

             j = nxt[j];

         }

     }

 }

 bool match(char *d, char *s, int ld, int ls) {

     int i = , j = ;

     while (i < ld) {

         if (d[i] == s[j]) {

             ++i;

             ++j;

         } else {

             j = nxt[j];

             if (j == -) {

                 j = ;

                 ++i;

             }

         }

         if (j == ls)

             return true;

     }

     return false;

 }

 void cover() {

     memset(visit, false, sizeof(visit));

     rep(i, , n) {

         getnext(word[i]);

         rep(j, , n) {

             if (i == j)

                 continue;

             if (match(word[j], word[i], Len[j], Len[i])) {

                 visit[i] = true;

                 break;

             }

         }

     }

     int nn = ;

     rep(i, , n) {

         if (!visit[i]) {

             strcpy(word[nn], word[i]);

             Len[nn] = strlen(word[nn]);

             ++nn;

         }

     }

     n = nn;

 }

 bool judge(int l, char *sa, char *sb) {

     rep(i, , l) {

         if (sa[i] != sb[i])

             return false;

     }

     return true;

 }

 int LongFix(int a, int b) {

     per(l, , Len[a]) {

         if (Len[b]>=l && judge(l, word[a]+Len[a]-l, word[b]))

             return l;

     }

     return ;

 }

 void calc() {

     rep(i, , n) {

         rep(j, , n) {

             if (i == j) {

                 M[i][j] = Len[i];

                 continue;

             }

             M[i][j] = LongFix(i, j);

         }

     }

 }

 void solve() {

     sort(a, a+n);

     n = unique(a, a+n) - a;

     rep(i, , n) {

         f(word[i], a[i]);

         Len[i] = strlen(word[i]);

     }

     cover();

     calc();

     int mst =  << n;

     memset(dp, INF, sizeof(dp));

     rep(i, , n)

         dp[<<i][i] = Len[i];

     rep(i, , mst) {

         rep(j, , n) {

             if (dp[i][j]==INF || (i&(<<j))==)

                 continue;

             rep(k, , n) {

                 if (i & (<<k))

                     continue;

                 int nst = i | (<<k);

                 dp[nst][k] = min(dp[nst][k], dp[i][j]+Len[k]-M[k][j]);

             }

         }

     }

     rep(i, , n)

         sw[i] = string(word[i]);

     int st = mst - ;

     int p = -;

     string str = "";

     while () {

         int mn = INF, v;

         string tstr, mnstr;

         rep(i, , n) {

             if ((st & (<<i)) == )

                 continue;

             int tmp = dp[st][i];

             if (p >= ) {

                 tmp -= M[p][i];

                 tstr = sw[i].substr(M[p][i]);

             } else {

                 tstr = sw[i];

             }

             if (tmp<mn || (tmp==mn && tstr<mnstr)) {

                 mn = tmp;

                 mnstr = tstr;

                 v = i;

             }

         }

         str += mnstr;

         p = v;

         st ^= ( << v);

         if (st == )

             break;

     }

     int length = str.length(), base = ;

     __int64 ans = ;

     per(i, , length) {

         if (str[i] == '')

             ans = (ans + base) % mod;

         base = (base + base) % mod;

     }

     printf("%I64d\n", ans);

 }

 int main() {

     ios::sync_with_stdio(false);

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     while (cin >> n) {

         rep(i, , n)

             cin >> a[i];

         solve();

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }