Problem: Today DZY begins to play an old game. In this game, he is in a big maze with n rooms connected by m corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly.

DZY has got lost in the maze. Currently he is in the first room and has k lives. He will act like the follows:

  * Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked. 
  * Then he will go through the corridor and then the process repeats. 



There are some rooms which have traps in them. The first room definitely has no trap, the n-th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the n-th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

Input

The first line contains three integers n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 105; 2 ≤ k ≤ 109).

The second line contains n integers, each of them is either 0 or 1. If the i-th number is 1, then the i-th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than 101. It is guaranteed that the first room has no trap, and the n-th room has a trap.

Then m lines follows. Each of them contains two integers ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi), meaning that current corridor connects two rooms ui and vi. It is guaranteed that the corridor system is connected.

Output

Print the only real number — the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

Examples

Input

5 5 3
0 0 1 0 1
1 2
2 3
3 4
4 5
1 2


Output

0.25000000


Input

3 2 2
0 1 1
1 2
2 3


Output

-0.00000000


Input

2 1 3
0 1
1 2


Output

1.00000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
const double inf = 1e121;
const double eps = 1e-10;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long randint(long long l, long long r) {
  long long out = rng() % (r - l + 1) + l;
  return out >= l ? out : out + r - l + 1;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (long long i = 0; i < static_cast<long long>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
template <typename A, typename B, typename C, typename D, typename E>
string to_string(tuple<A, B, C, D, E> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + "," +
         to_string(get<4>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename T>
struct is_pair {
  static const bool value = false;
};
template <typename T, typename U>
struct is_pair<std::pair<T, U>> {
  static const bool value = true;
};
const long long INF = 0x3f3f3f3f3f3f3f3fll;
template <typename T>
typename enable_if<!is_integral<T>::value && !is_pair<T>::value, void>::type
read(T &x) {
  cin >> x;
}
long long read() {
  char c;
  long long out = 0, f = 1;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) {
  }
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) out = (out << 3) + (out << 1) + c - '0';
  return out * f;
}
template <typename T>
typename enable_if<is_integral<T>::value, T>::type read(T &x) {
  char c;
  T f = 1;
  x = 0;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) {
  }
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  return x *= f;
}
char read(char &x) {
  for (x = getchar(); isspace(x); x = getchar()) {
  }
  return x;
}
double read(double &x) {
  scanf("%lf", &x);
  return x;
}
template <typename T>
typename enable_if<!is_integral<T>::value && !is_pair<T>::value, void>::type
write(const T &x) {
  cout << x;
}
template <typename T>
typename enable_if<is_integral<T>::value, void>::type write(const T &x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
void write(const char &x) { putchar(x); }
void write(const double &x) { printf("%.12lf", x); }
template <typename T>
typename enable_if<is_pair<T>::value, void>::type read(T &x) {
  read(x.first);
  read(x.second);
}
template <typename T>
typename enable_if<is_pair<T>::value, void>::type write(const T &x) {
  write(x.first);
  putchar(' ');
  write(x.second);
}
template <typename T, typename... Args>
void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
template <
    typename OutputIt,
    typename = typename enable_if<
        is_same<output_iterator_tag,
                typename iterator_traits<OutputIt>::iterator_category>::value ||
        (is_base_of<forward_iterator_tag, typename iterator_traits<OutputIt>::
                                              iterator_category>::value &&
         !is_const<OutputIt>::value)>::type>
void read(OutputIt __first, OutputIt __last) {
  for (; __first != __last; ++__first) read(*__first);
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wts(InputIt __first, InputIt __last) {
  bool isFirst = true;
  for (; __first != __last; ++__first) {
    if (isFirst)
      isFirst = false;
    else
      putchar(' ');
    write(*__first);
  }
  putchar('\n');
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wtb(InputIt __first, InputIt __last) {
  for (; __first != __last; ++__first) {
    write(*__first);
    putchar('\n');
  }
}
template <typename T>
void wts(const T &x) {
  write(x);
  putchar(' ');
}
template <typename T>
void wtb(const T &x) {
  write(x);
  putchar('\n');
}
template <typename T>
void wte(const T &x) {
  write(x);
  exit(0);
}
template <typename T, typename... Args>
void wts(const T &x, Args... args) {
  wts(x);
  wts(args...);
}
template <typename T, typename... Args>
void wtb(const T &x, Args... args) {
  wts(x);
  wtb(args...);
}
template <typename T, typename... Args>
void wte(const T &x, Args... args) {
  wts(x);
  wte(args...);
}
template <typename T1, typename T2>
inline bool up(T1 &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T1, typename T2>
inline bool dn(T1 &x, const T2 &y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T1, typename T2, typename T3>
inline bool inRange(const T1 &x, const T2 &l, const T3 &r) {
  return !(x < l) && !(r < x);
}
template <typename T1, typename T2>
inline auto minOfDifferentTypes(const T1 &x, const T2 &y)
    -> decltype(x < y ? x : y) {
  return x < y ? x : y;
}
template <typename T1, typename T2>
inline auto maxOfDifferentTypes(const T1 &x, const T2 &y)
    -> decltype(x < y ? y : x) {
  return x < y ? y : x;
}
template <typename T1, typename T2, typename T3>
inline T1 &madd(T1 &x, const T2 &y, const T3 &modulo) {
  return x = (long long)(x + y + modulo) % modulo;
}
template <typename T1, typename T2, typename T3>
inline T1 &mmul(T1 &x, const T2 &y, const T3 &modulo) {
  return x = (long long)x * y % modulo;
}
inline long long modadd(long long x, long long y, long long modulo) {
  return (x + y) >= modulo ? x + y - modulo : x + y;
}
inline long long isinf(long long x) { return x < INF ? x : -1; }
inline void yesno(bool x) { wtb(x ? "Yes" : "No"); }
struct Matrix {
  long long n;
  vector<vector<double>> a;
  Matrix(long long _n) : n(_n), a(n, vector<double>(n)) {}
  Matrix operator*(const Matrix &b) const {
    Matrix res(n);
    for (long long i = (0), iend = (n - 1); i <= iend; ++i) {
      for (long long j = (0), jend = (n - 1); j <= jend; ++j) {
        for (long long k = (0), kend = (n - 1); k <= kend; ++k) {
          res.a[i][j] += a[i][k] * b.a[k][j];
        }
      }
    }
    return res;
  }
  Matrix qpow(long long y) {
    Matrix x = *this;
    Matrix res(n);
    for (long long i = (0), iend = (n - 1); i <= iend; ++i) res.a[i][i] = 1;
    while (y) {
      if (y & 1) res = res * x;
      x = x * x;
      y >>= 1;
    }
    return res;
  }
};
signed main() {
  long long n, m, K;
  read(n, m, K);
  vector<long long> isTrap(n + 1), trap, id;
  for (long long i = (1), iend = (n); i <= iend; ++i)
    if (read(isTrap[i])) {
      id.push_back(trap.size());
      trap.push_back(i);
    }
  vector<vector<long long>> g(n + 1);
  for (long long i = (1), iend = (m); i <= iend; ++i) {
    long long u, v;
    read(u, v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<vector<double>> a(n + 1, vector<double>(n + 1));
  for (long long u = (1), uend = (n); u <= uend; ++u) {
    a[u][u] = 1;
    if (!isTrap[u]) {
      for (auto v : g[u]) {
        a[u][v] -= 1.0 / g[u].size();
      }
    }
  }
  vector<vector<double>> inv(n + 1, vector<double>(n + 1));
  for (long long i = (1), iend = (n); i <= iend; ++i) inv[i][i] = 1;
  for (long long i = (1), iend = (n - 1); i <= iend; ++i) {
    for (long long j = (i), jend = (n); j <= jend; ++j) {
      if (fabs(a[j][i]) > eps) {
        swap(a[i], a[j]);
        break;
      }
    }
    for (long long j = (i + 1), jend = (n); j <= jend; ++j) {
      double mul = a[j][i] / a[i][i];
      for (long long k = (1), kend = (n); k <= kend; ++k) {
        a[j][k] -= a[i][k] * mul;
        inv[j][k] -= inv[i][k] * mul;
      }
    }
  }
  for (long long i = (n), iend = (2); i >= iend; --i) {
    {
      double mul = 1 / a[i][i];
      for (long long j = (1), jend = (n); j <= jend; ++j) inv[i][j] *= mul;
    }
    for (long long j = (1), jend = (i - 1); j <= jend; ++j) {
      double mul = a[j][i];
      for (long long k = (1), kend = (n); k <= kend; ++k)
        inv[j][k] -= inv[i][k] * mul;
    }
  }
  vector<vector<double>> b(n + 1, vector<double>(trap.size()));
  for (long long i = (0), iend = (trap.size() - 1); i <= iend; ++i) {
    for (long long u = (1), uend = (n); u <= uend; ++u) {
      b[u][i] = inv[u][trap[i]];
    }
  }
  Matrix mat(trap.size());
  for (long long i = (0), iend = (trap.size() - 1); i <= iend; ++i) {
    for (long long j = (0), jend = (trap.size() - 1); j <= jend; ++j) {
      for (auto v : g[trap[i]]) {
        mat.a[i][j] += b[v][j] / g[trap[i]].size();
      }
    }
  }
  42;
  42;
  mat = mat.qpow(K - 2);
  42;
  double ans = 0;
  for (long long i = (0), iend = (trap.size() - 1); i <= iend; ++i)
    ans += b[1][i] * mat.a[i][trap.size() - 1];
  wtb(ans);
  return 0;
}