問題文
N個の球と、N-1本のロープがあります。
ロープは2つの球を結んでいます。
また、全ての球はロープによって結ばれ、どの2つの球についてもロープをたどって1つめの球から2つめの球に行くことができます。（つまり連結です。）
あなたは、球を以下の条件で色塗りします。色は1～SのS色です。
・隣り合う（ロープで直接結ばれた）球同士の色の差はU以内である。
また、あなたはM回のクエリを処理しなければなりません。これは以下の様なものです。
・i番目のロープを切る。
そのとき、最初の状態と、
各クエリを行った後それぞれの状態についての色塗りの通り数を求めなさい。
入力
1行目には、球の個数Nと、クエリの個数Mと、色の種類数S、
許される差の上限Uが空白区切りで与えられます。
・ 続くN-1行には、A[i], B[i]が与えられます。これは、i番目のロープがA[i]とB[i]を結んでいることを意味します。
・ 続くM行にはC[i]が与えられます。これは、i個目のクエリでロープC[i]を削除することを意味します。なお、i≠jのとき、C[i]≠C[j]を満たします。
出力
各クエリに対し、塗り方の通り数を 1 000 000 007で割ったあまりを出力せよ。
なお、最初の状態での出力を忘れないこと。
制約
すべての入力データは以下の条件を満たす。- 2≦N, S, U≦200
- 0≦M≦N - 1
- 1≦A[i], B[i]≦N
- 1≦C[i]≦N-1
入出力例
入力例1
3 2 3 1 1 2 2 3 1 2
出力例1
17 21 27
入力例2
4 3 3 1 1 2 1 3 1 4 2 3 1
出力例2
43 51 63 81