#16 「 瓶颈 」

统计

相信考过noip的同学,一定都认识在一位在树上跑运输的货车司机。

现在这个司机转行在有单行道的bj市开短途货车,bj市的地图有$n$个点$m$条边,每条单向边从$a_i$出发通向$b_i$,最大载重量为$w_i$。

他想要从$s$点开到$t$点,假设他一次最多可以运送的货物为$capacity(s,t)$

他想要知道$\sum_{t \not= s} capacity(s, t)$是多少?

输入格式

一行一个整数$T$,表示数据组数。

每组数据第一行三个整数$n, m, s$。

接下来五个数字$c_0, c_1, c_2, c_3, k$,表示

$a_i = (c_3 (3i + 1)^3 + c_2 (3i + 1)^2 + c_1 (3i + 1)^1 + c_0) \mod 998244353 \mod n + 1$,

$b_i = (c_3 (3i + 2)^3 + c_2 (3i + 2)^2 + c_1 (3i + 2)^1 + c_0) \mod 998244353 \mod n + 1$,

$w_i = (c_3 (3i + 3)^3 + c_2 (3i + 3)^2 + c_1 (3i + 3)^1 + c_0) \mod 998244353 \mod k + 1$。

输出格式

$T$行,每行一个整数表示答案。

样例数据

input

2
100 1000 4
413 432 342 34221 324423
10 20 5
421 324 4321 4324 423432

output

27659886
475194

数据规模与约定

$T \leq 100, \sum n \leq 2 \times 10^5, \sum m \leq 2 \times 10^6, \sum k \leq 2 \times 10^6$

时间限制:1s

空间限制:512MB

Author: whx