2
0 1
 1
0

1
2
 1

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long double PI = acos((long double)-1.0);
int n, i, j, k, a;
struct str {
  unsigned long long a[10];
} f[N], nf[N];
void operator*=(str &a, str b) {
  str c;
  memset(c.a, 0, sizeof(c.a));
  int i, j;
  for (i = 0; i < 10; ++i)
    for (j = 0; j < 10; ++j) c.a[(i + j) % 10] += a.a[i] * b.a[j];
  a = c;
}
void operator+=(str &a, str b) {
  int i;
  for (i = 0; i < 10; ++i) a.a[i] += b.a[i];
}
str ofs(str a, int x) {
  str c;
  x %= 10;
  for (i = 0; i < 10; ++i) c.a[i] = a.a[(i + 10 - x) % 10];
  return c;
}
str qpow(str a, int b) {
  str s = a, ans;
  memset(ans.a, 0, sizeof(ans.a));
  ans.a[0] = 1;
  while (b) {
    if (b & 1) ans *= s;
    s *= s;
    b >>= 1;
  }
  return ans;
}
unsigned long long qpow(unsigned long long a, unsigned long long b,
                        unsigned long long M) {
  unsigned long long s = a, ans = 1;
  while (b) {
    if (b & 1) ans = ans * s % M;
    s = s * s % M;
    b >>= 1;
  }
  return ans;
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d", &a);
    ++f[a].a[0];
  }
  int ul = 1;
  for (i = 0; i < 5; ++i, ul *= 10) {
    for (j = 0; j < 100000; ++j) memset(nf[j].a, 0, sizeof(nf[j].a));
    for (j = 0; j < 10; ++j)
      for (k = 0; k < 100000; ++k)
        nf[j * ul + k % ul + k / ul / 10] += ofs(f[k], j * (k / ul % 10));
    for (j = 0; j < 100000; ++j) f[j] = nf[j];
  }
  for (i = 0; i < 100000; ++i) f[i] = qpow(f[i], n);
  ul = 1;
  for (i = 0; i < 5; ++i, ul *= 10) {
    for (j = 0; j < 100000; ++j) memset(nf[j].a, 0, sizeof(nf[j].a));
    for (j = 0; j < 10; ++j)
      for (k = 0; k < 100000; ++k)
        nf[j * ul + k % ul + k / ul / 10] += ofs(f[k], -j * (k / ul % 10));
    for (j = 0; j < 100000; ++j) f[j] = nf[j];
  }
  for (i = 0; i < n; ++i) {
    long double ans = 0;
    for (j = 0; j < 10; ++j) ans += cos(2 * PI / 10 * j) * f[i].a[j];
    unsigned long long s = ans;
    printf("%llu\n",
           (s * qpow(5, (1ull << 58) - 1, (1ull << 58)) >> 1) % (1ull << 58));
  }
}
