题面 样例

题目描述

有一个字符集为 $C$ 的字符串，初始形如：从左往右形成了 $n$ 段，第 $i$ 段有 $B_i$ 个字符 $A_i(1\le A_i\le C)$（不保证 $A_i\neq A_{i+1}$）。你可以进行至多 $k$ 次操作，每次操作形如选择一个区间 $[l,r]$ 和任意一个字符，然后把字符串的 $[l,r]$ 段全部修改成该字符，一个位置只能被选择一次，问可以得到多少本质不同的字符串。对 $10^9+7$ 取模。

输入格式

从 color.in 中读入。

第一行三个正整数 $n,C,k$。

接下来 $n$ 行，每行两个正整数 $A_i,B_i$。

输出格式

输出到 color.out 中。

输出答案对 $10^9+7$ 取模的结果。

样例输入 1

2 3 2
1 2
2 2

样例输出 1

57

数据范围

对于所有数据，保证 $n,k\le 7,B_i,C\le 10^9$。

对于测试点 $1\sim 2$，满足 $C,k\le 3,\sum B_i\le 5$。

对于测试点 $3\sim 4$，满足 $k=1$。

对于测试点 $5\sim 6$，满足 $n=1$。

对于测试点 $7\sim 8$，满足 $n,k\le 5,B_i,C\le 100$。

对于测试点 $9\sim 10$，无特殊约束。