给定一张 $n$ 个点 $m$ 条边的无重边无自环的有向图，你要从 $1$ 号点到 $n$ 号点去。

如果你在 $t$ 时刻之后到达 $n$ 号点，你要交 $x$ 元的罚款。

每条边从 $a_i$ 到 $b_i$，走过它需要花费 $c_i$ 元，多次走过同一条边需要多次花费。

走过每条边所需的时间是随机的，对于 $k \in [1,t]$，$\frac{p_{i,k}}{10^5}$ 表示走过第 $i$ 条边需要时间 $k$ 的概率。因此如果多次走过同一条边，所需的时间也可能不同。

你希望花费尽可能少的钱（花费与罚款之和）到达 $n$ 号点，因此每到达一个点，你可能会更改原有的计划。

求在最优决策下，你期望花费的钱数。

$n \le 50$，$m \le 100$，$t \le 2 \times 10^4$，$x,c_i \le 10^6$，$\sum_{k=1}^t p_{i,k} = 10^5$，答案精度误差 $\le 10^{-6}$。

给出一个门限值 $k$ 和两个只包含 $\texttt{AGCT}$ 四种字符的基因串 $S$ 和 $T$。现在你要找出在下列规则中 $T$ 在 $S$ 中出现了几次。

$T$ 在 $S$ 的第 $i$ 个位置中出现，当且仅当把 $T$ 的首字符和 $S$ 的第 $i$ 个字符对齐后，$T$ 中的每一个字符能够在 $S$ 中找到一个位置偏差不超过 $k$ 的相同字符。

即对于所有的 $j \in[1,|T|]$，都存在一个 $p \in [1,|S|]$ 使得 $|(i+j-1)-p| \leq k$ 且 $S_p=T_j$ 。

例如 $k=1$ 时，$\texttt{ACAT}$ 出现在 $\texttt{AGCAATTCAT}$ 的 $2$ 号， $3$ 号和 $6$ 号位置。 (编号从 $1$ 开始。)

给出一个长度为n的序列 $a_1,a_2...a_n$。求构造出一个序列 $i_1 < i_2 < ... < i_k(1\le{k}\le{n})$ 使得 $a_{i_1}\&a_{i_2}\&...\&a_{i_k}=0$。求方案数模 $10^9+7$。

也就是从$\{a_i\}$ 里面选出一个非空子集使这些数按位与起来为0。