TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

53.8% (7/13)

Submission's AC Ratio

25.8% (23/89)

Tags

Description

最近各種DIY的小型吊飾十分熱門,不只可以讓人享受手作的樂趣,還能自己挑選喜歡的款式,因而受到大眾的喜愛。一年前,你跟一些朋友買過用圓方珠子串起來的吊飾,現在你迷上了另一種飾品:由一些彩色珠子串起來的項鍊。這些珠子由兩個不同顏色的寶石拼接組成,而你希望選一些珠子串成一個項鍊,使得相鄰兩個珠子的端點顏色必須相同。

舉例來說,假設有三個珠子,兩端顏色分別為 紅+藍、綠+藍、綠+紅,那我們可以用 紅+藍、藍+綠、綠+紅 的順序,串成一個項鍊,注意到由於項鍊是環狀的,結尾顏色須與第一個顏色相同。

飾品店裡有 $n$ 種珠子,其中可能會出現 $k$ 種顏色,編號為 $1$ 到 $k$。第 $i$ 種珠子有賣 $w_i$ 個不同的珠子(種類一樣,但在選擇的時候仍算是不同的)。你想要買一些(至少一個)珠子符合以下條件:
* 每一種珠子只出現一次(注意顏色 $(1, 2)$ 跟 $(2, 1)$ 視為同一種珠子)
* 買的珠子可以拿來串成若干個項鍊,也就是每個珠子出現在恰一個項鍊中

請問有多少種買珠子的方法符合條件?由於答案可能很大,請輸出方法數模 $10 ^ 9 + 7$。

Input Format

第一行輸入兩個整數 $k, n$,意義如題目所述。
接下來 $n$ 行有三個整數 $a_i, b_i, w_i$,代表第 $i$ 種珠子的顏色組合是 $(a_i, b_i)$,且店裡有 $w_i$ 個。

對於所有測資:$k \leq 23, n \leq \frac{k(k-1)}{2}, 1 \leq w_i \leq 10 ^ 9$
$1\leq a_i, b_i \leq n, a_i \neq b_i$,保證一種珠子至多只會出現一次。

Output Format

輸出一個整數,代表答案模 $10 ^ 9 + 7$。

Sample Input 1

3 3
1 2 2
2 3 3
3 1 2

Sample Output 1

12

Sample Input 2

4 5
1 2 4
2 3 5
3 1 2
1 4 7
4 3 3

Sample Output 2

502

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~11 $n \leq 20$ 13
3 12~21 $k \leq 19$ 35
4 0~31 無其他限制 52

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524188 65536 1 4
1 2000 524188 65536 1 4
2 2000 524188 65536 2 4
3 2000 524188 65536 2 4
4 2000 524188 65536 2 4
5 2000 524188 65536 2 4
6 2000 524188 65536 2 4
7 2000 524188 65536 2 4
8 2000 524188 65536 2 4
9 2000 524188 65536 2 4
10 2000 524188 65536 2 4
11 2000 524188 65536 2 4
12 2000 524188 65536 3 4
13 2000 524188 65536 3 4
14 2000 524188 65536 3 4
15 2000 524188 65536 3 4
16 2000 524188 65536 3 4
17 2000 524188 65536 3 4
18 2000 524188 65536 3 4
19 2000 524188 65536 3 4
20 2000 524188 65536 3 4
21 2000 524188 65536 3 4
22 3000 524188 65536 4
23 3000 524188 65536 4
24 3000 524188 65536 4
25 3000 524188 65536 4
26 3000 524188 65536 4
27 3000 524188 65536 4
28 3000 524188 65536 4
29 3000 524188 65536 4
30 3000 524188 65536 4
31 3000 524188 65536 4