#1200. 「HB 省队互测 2019 Round1 Day2」游戏

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: huyufeifei

题目描述

北斗是一个爱玩游戏的女孩子。


北斗有 n 部游戏要玩,这些游戏以 0\sim n-1 标号。她准备花连续的若干天来玩游戏。每天她至少会玩一部游戏,且不会玩之前已经玩过的游戏。对于每一天,北斗每玩一部游戏,就能够得到一点愉悦值。特别地,有若干对游戏题材相同,或者画师相同,或者是前后作的关系。如果某一对游戏在同一天玩,北斗就会额外获得若干愉悦值。而北斗玩这 n 部游戏的总愉悦值就是每一天的愉悦值之积。

北斗认为两种方案不同,当且仅当存在某一部游戏满足,北斗在这两种方案中不是同一天玩它。

现在北斗想要知道,对于所有的玩游戏方案,她能够得到的愉悦值之和是多少。你很喜欢吃北斗做的菜。为了吃到美味的晚饭,你只好帮助北斗解决这个问题。

输入格式

第一行输入两个非负整数 n m ,表示游戏个数和有关联的游戏对数。

接下来 m 行,每行输入三个非负整数 a b c ,表示如果编号为 a b 的游戏在同一天玩,北斗在当天会额外获得 c 的愉悦值。

输出格式

输出一行一个数,表示所有方案北斗能得到的愉悦值之和。由于答案可能很大,只需输出答案对 100000007 (一个大质数)取模后的结果即可。

样例

样例 1 输入

3 2
2 0 68
1 0 91

样例 1 输出

498

样例 1 解释

对于某一天,玩 0 号游戏的愉悦值是 1 ,玩 1 号游戏的愉悦值是 1 ,玩 2 号游戏的愉悦值是 1 ,玩 0,1 号游戏的愉悦值是 93 ,玩 1,2 号游戏的愉悦值是 2 ,玩 0,2 号游戏的愉悦值是 70 ,玩 0,1,2 号游戏的愉悦值是 162

假如分三天玩完,有 3!=6 种方案,每种方案的愉悦值是 1 ,总共能得到 6 点愉悦值。

假如分两天玩完,那么有一天玩两部游戏,还有一天玩一部游戏。

当单独玩 0 号游戏时,这两天的愉悦值是 2

当单独玩 1 号游戏时,这两天的愉悦值是 70

当单独玩 2 号游戏时,这两天的愉悦值是 93

这三种情况又都有先后顺序之分,总共有 6 种方案,愉悦值总和为 330

假如分一天玩完,那么只有一种方案,愉悦值为 162

总愉悦值为 498

样例 2 输入

5 0

样例 2 输出

1305

数据范围与提示

测试点编号 n m
1\sim 4 \le 6 \le 100000
5\sim 10 \le 15
11\sim 12 \le 19 \le 0
13\sim 20 \le 100000

对于全部数据,保证 n\ge 0,m\ge 0,1\le c\le 100 0\le a,b\le n-1 ,不存在两对关系所涉及的两个游戏分别相同或者某对关系的 a b 相同。