DHBB112021_KIOSKS

#define task "KIOSKS"
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

using ll = long long;

void read(int &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr int N = 1e4 + 5;
constexpr ll mod = 1e9 + 7;
ll ans(0);
ll dp[N];
int n, k, a[N], cnt[N], l(0), id[N];
vector<int> adj[N];
bool Sub2(1);

void Read()
{

    //cin >> n >> k;
    read(n), read(k);
    for (int i = 1; i <= n; ++i)
        //cin >> a[i];
        read(a[i]);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        //cin >> u >> v;
        read(u), read(v);
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        Sub2 = Sub2 && ((int)adj[u].size() <= 2) && ((int)adj[v].size() <= 2);
    }
}

#define bit(i, x) (((x) >> (i)) & 1)

/// dp[i]: số cách chọn các ki ốt để giữ lại sao cho PHẢI chứa i và không được chứa ki ốt nào bán loại hàng được bật trong mask

void dfs_1(int v, int p, int mask, int sign)
{
    dp[v] = 1;
    if (a[v] <= k && bit(a[v] - 1, mask))
        dp[v] = 0;

    for (auto i : adj[v])
        if (i != p)
        {
            dfs_1(i, v, mask, sign);
            dp[v] = dp[v] * (dp[i] + 1) % mod;
        }

    (ans += sign * dp[v]) %= mod;
}

void Sub_3()
{
    /// bao hàm loại trừ
    for (int i = 0; i < (1 << k); ++i)
        dfs_1(1, 0, i, (__builtin_popcount(i) & 1) ? -1 : 1);
    cout << (ans + mod) % mod;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Sub_3();
}