P0007

二叉树美观度

二叉树美观度

定义一棵有根二叉树满足以下条件：

  • 每个非叶节点恰有两个儿子，分别记为左儿子和右儿子；
  • 整棵树恰有 nn 个叶子节点。

对于这棵树上的每个节点，定义其美观度如下：

  • 每个叶子节点的美观度为 11；
  • 对于每个非叶节点，设其左子树中的叶子节点个数为 xx。若存在某条给定信息满足 si=xs_i = x，则该节点的美观度为对应的 viv_i；否则该节点的美观度为 AA。

保证输入中的 sis_i 两两不同。

定义一棵二叉树的美观度为这棵树上所有节点美观度的乘积。

现在考虑所有满足条件的有根二叉树。请你求出这些二叉树的美观度之和。

答案可能很大，你只需要输出答案对 109+710^9+7 取模后的结果。

输入格式

第一行三个整数 n,k,An, k, A。

接下来 kk 行，每行两个整数 si,vis_i, v_i，表示一条信息。

输出格式

输出一行一个整数，表示答案对 109+710^9+7 取模后的结果。

样例 1

输入

5 1 1
2 2

输出

25

样例 2

输入

6 2 1
2 3
4 5

输出

268

提示

本题共 2020 组数据。

数据点编号特殊性质
1∼41 \sim 4n≤103, k>0, A>0n \le 10^3,\ k > 0,\ A > 0
5∼65 \sim 6k=0, n>5×104k = 0,\ n > 5 \times 10^4
7∼87 \sim 8A=0, n>5×104, k>0A = 0,\ n > 5 \times 10^4,\ k > 0
9∼129 \sim 12103<n≤5×104, k>0, A>010^3 < n \le 5 \times 10^4,\ k > 0,\ A > 0
13∼2013 \sim 20无特殊性质

对于所有数据，1≤n≤1061 \le n \le 10^6，0≤k≤100 \le k \le 10，1≤si<n1 \le s_i < n，0≤vi,A<109+70 \le v_i, A < 10^9+7，并保证任意两个 sis_i 互不相同。