נתון עץ עם $N$ צמתים ו-$N - 1$ קשתות, שבו לכל קשת $i$ יש רמת מורכבות $l_i$. המרחק $d(u, v)$ בין שני צמתים $u$ ו-$v$ הוא סכום רמות המורכבות לאורך המסלול היחיד ביניהם בעץ. שים לב ש-$d(u, v) = d(v, u)$ ו-$d(v, v) = 0$.

ישנן $M$ חידות, וכל חידה $i$ דורשת $k_i$ פיסות מידע, הממוקמות לאורך קשתות מסוימות בעץ. ייתכן שמספר פיסות מידע יימצאו על אותה קשת!

עבור כל שני צמתים $S$ ו-$T$, מסע בין $S$ ל-$T$ הוא מוצלח אם לאורך המסלול מ-$S$ ל-$T$, נאספות כל פיסות המידע הדרושות עבור כל חידה שנתקלים בה. באופן ספציפי, חידה נחשבת לפתירה במהלך מסע אם נתקלים בכל פיסות המידע הנדרשות עבור אותה חידה לאורך המסלול.

המשימה היא לחשב את סכום המרחקים עבור כל המסעות המוצלחים בין כל שני צמתים $S$ ו-$T$ (כאשר $1 \le S \le T \le N$), מודולו $10^9 + 7$.

באופן פורמלי, המשימה היא לחשב:

$$\sum_{\substack{1 \le S \le T \le N, \\ \text{journey } (S, T) \text{ is successful}}} d(S, T)$$

החל מצומת $S$, עליך לנוע לצומת אחר $T$ לאורך המסלול היחיד בעץ. לאורך הדרך, כל פיסת מידע הממוקמת על קשתות המסלול הזה תיאסף אוטומטית. כדי שהמסע מ-$S$ ל-$T$ ייחשב למוצלח, עליו לעמוד בתנאי הבא:

• תהא $O$ קבוצת החידות שעבורן נאספה לפחות פיסת מידע אחת במהלך המסע. המסע מוצלח אם ורק אם נאספו כל פיסות המידע הנדרשות כדי לפתור כל חידה בקבוצה $O$. במילים אחרות, עליך לאסוף כל פיסת מידע הדרושה כדי לפתור באופן מלא כל חידה ב-$O$.

קלט

השורה הראשונה מכילה שני מספרים שלמים מופרדים ברווחים $N$ ו-$M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

לאחר מכן מופיעות $N - 1$ שורות, שכל אחת מהן מכילה שלושה מספרים שלמים מופרדים ברווחים $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), המתארים קשת $i$ המחברת את הצמתים $a_i$ ו-$b_i$ עם מורכבות $l_i$.

לאחר מכן מופיעות ההגדרות של $M$ חידות. עבור כל חידה $i$, הקלט מתחיל בשורה אחת המכילה את $k_i$ ואחריו $k_i$ מספרים שלמים מופרדים ברווחים $u_{i_1}, u_{i_2}, \dots, u_{i_{k_i}}$ ($0 \le k_i \le K, 1 \le u_{i_j} \le N - 1$), כאשר $u_{i_j}$ הם האינדקסים של הקשתות שעליהן ממוקמות פיסות המידע הנדרשות לפתרון החידה.

כאן, $K$ הוא סכום כל ערכי $k_i$ על פני כל החידות, ומובטח כי $1 \le K \le 10^6$.

פלט

הדפס שורה אחת המכילה מספר שלם אחד, התשובה לבעיה מודולו $10^9 + 7$.

דוגמה

קלט לדוגמה 1

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

פלט לדוגמה 1

17

הערה

איור 1. מבנה העץ. המעוינים הם פיסות המידע, והערכים על הקשתות הם רמות המורכבות.