2
0 1
 1
0

1
2
 1

#include <bits/stdc++.h>
using namespace std;
const unsigned long long m = 1llu << 58;
const int n = 100000;
struct num {
  num() { p = q = 0; }
  num(unsigned long long x) {
    p = x / n;
    q = x % n;
  }
  unsigned long long p, q;
  num operator+(num t) {
    num r;
    r.p = p + t.p;
    r.q = q + t.q;
    r.p += r.q / n;
    r.q %= n;
    return r;
  }
  num operator-(num t) {
    num r;
    r.p = p >= t.p ? p - t.p : p + m - t.p;
    r.q = q - t.q;
    if (r.q < 0) {
      if (r.p == 0)
        r.p = m - 1;
      else
        r.p--;
      r.q += n;
    }
    return r;
  }
  num operator*(num t) {
    num r;
    r.p = p * t.p * n + p * t.q + t.p * q;
    r.q = q * t.q;
    r.p += r.q / n;
    r.q %= n;
    return r;
  }
  bool operator<(const num &t) const {
    if (p != t.p) return p < t.p;
    return q < t.q;
  }
} I[n];
const int per = 10;
struct comp {
  comp() {
    for (int i = 0; i < per; i++) a[i] = num();
  }
  num a[per];
  comp operator*(comp t) {
    comp r;
    for (int i = 0; i < per; i++)
      if (a[i].p || a[i].q)
        for (int j = 0; j < per; j++)
          if (t.a[j].p || t.a[j].q)
            r.a[(i + j) % per] = (r.a[(i + j) % per] + a[i] * t.a[j]);
    return r;
  }
  void reg() {
    for (int i = 0; i < per; i++) a[i].p %= m;
    for (int u : {1, 2, 5}) {
      for (int s = 0; s < u; s++) {
        auto mn = a[s];
        for (int k = s + u; k < per; k += u) mn = min(mn, a[k]);
        if (mn.p || mn.q) {
          for (int k = s; k < per; k += u) a[k] = a[k] - mn;
        }
      }
    }
  }
} A[n], B[n];
comp fpow(comp a, int p) {
  comp r;
  r.a[0] = 1;
  a.reg();
  while (p) {
    if (p & 1) r = r * a, r.reg();
    a = a * a;
    a.reg();
    p /= 2;
  }
  return r;
}
int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    int x;
    scanf("%d", &x);
    I[x].q++;
  }
  for (int i = 0; i < n; i++) A[i].a[0] = I[i];
  for (int i = 1; i < n; i *= per) {
    for (int s = 0; s < n; s += i * per)
      for (int v = 0; v < i; v++) {
        for (int j = 0; j < per; j++) {
          comp c;
          for (int k = 0; k < per; k++) {
            auto &u = A[s + v + k * i];
            int d = (j * k) % per;
            for (int l = 0; l < per; l++)
              if (u.a[l].p || u.a[l].q) {
                auto &a = c.a[(d + l) % per];
                a = a + u.a[l];
              }
          }
          c.reg();
          B[s + v + j * i] = c;
        }
      }
    memcpy(A, B, sizeof(A));
  }
  for (int j = 0; j < n; j++) A[j] = fpow(A[j], N);
  for (int i = 1; i < n; i *= per) {
    for (int s = 0; s < n; s += i * per)
      for (int v = 0; v < i; v++) {
        for (int j = 0; j < per; j++) {
          comp c;
          for (int k = 0; k < per; k++) {
            auto &u = A[s + v + k * i];
            int d = per - (j * k) % per;
            for (int l = 0; l < per; l++)
              if (u.a[l].p || u.a[l].q) {
                auto &a = c.a[(d + l) % per];
                a = a + u.a[l];
              }
          }
          c.reg();
          B[s + v + j * i] = c;
        }
      }
    memcpy(A, B, sizeof(A));
  }
  for (int j = 0; j < N; j++) {
    printf("%llu\n", (A[j].a[0] + A[j].a[1]).p % m);
  }
  return 0;
}
