Comet OJ

C1189 [Contest #0]旅途

内存限制：1024 MB 时间限制：2000 ms

题目描述

小象来到了百特国旅游。百特国有 $n$ 所城市，这些城市围成了一个圈。小象按照顺时针给这些城市从 $1$ 到 $n$ 编号，其中 $1$ 号城市是他最先到达的城市。

小象患有选择困难症。他在旅游之前并没有制定合理的旅游计划，而是决定用一个随机策略来访问这些城市。

小象共有 $m$ 天的旅游时间。在第一天里，小象会选择游玩 $1$ 号城市。而在接下来的每一天，他有 $p\%$ 的概率去前一天游玩城市顺时针方向的下一个城市游玩，有 $q\%$ 的概率去逆时针方向的下一个城市游玩，也有 $(100 - p - q)\%$ 的概率继续停留在前一天的城市游玩。

他很好奇他平均可以游玩到多少个不同的城市，你可以帮他计算一下吗？不妨设他能恰好游玩到 $i$ 个城市的概率是 $f(i)$，在给定正整数 $k$ 的情况下，请你计算 $100^{m - 1} \sum\limits_{i = 1}^{n}{i^k f(i)}$ 对 $(10^9 + 7)$ 取模的值。

不难证明 $100^{m - 1} \sum\limits_{i = 1}^{n}{i^k f(i)}$ 是一个整数，它对 $(10^9 + 7)$ 取模的值也是明确的、良定义的。

输入格式

输入包含多组测试数据。输入的第一行包含一个正整数 $T$ ($1 \leq T \leq 500$)，表示测试数据的组数。接下来依次描述每组测试数据，对于每组测试数据：

仅一行，包含五个整数 $n$, $m$, $k$, $p$ 和 $q$ ($1 \leq n, m, k \leq 500$, $p, q \geq 0$, $p + q \leq100$)，含义如题面所示。

保证所有测试数据的 $n$ 之和不超过 $1000$，所有测试数据的 $m$ 之和不超过 $1000$。

输出

对于每组数据，输出一行，包含一个整数，表示所求的值。

样例

样例输入 1

3
5 5 1 25 25
5 5 2 50 50
5 5 3 0 100

样例输出 1

246093750
212499993
499999916

提示

对于第三组样例数据，小象一定会游玩到所有城市，故所求为 $\left(100^4 \times 5^3\right) \bmod (10^9 + 7) = 499999916$。