#P17506. PM14126 袋子与卡片

PM14126 袋子与卡片

题目描述

有 nn 个袋子,编号为 0,1,…,n−10,1,\ldots,n-1。每个袋子中有很多卡片,每张卡片上写着一个 00 到 m−1m-1 的整数。

记 cnti,jcnt_{i,j} 为袋子 ii 中数字 jj 的卡片数量。给定 x,a,b,cx,a,b,c,所有 cnti,jcnt_{i,j} 按如下顺序生成,其中所有运算均使用足够大的整数类型:

for i = 0 .. n-1:
    for j = 0 .. m-1:
        cnt[i][j] = x
        x = ((x * a + b) xor c) mod 1000000007

长度为 2m−12m-1 的字符串 isGood 描述哪些和是“好数”:当且仅当 isGood[k] = 'Y' 时,整数 kk 是好数。

对于两个袋子 i<ji<j,定义 ansi,jans_{i,j} 为:分别从袋子 ii 和袋子 jj 中选择一张卡片,使两张卡片上的数字之和为好数的方案数。

你需要计算所有 ansi,jans_{i,j},并输出

$\displaystyle \bigoplus_{0\le i<j<n}(ans_{i,j}\bmod 1000000007)$,

其中 ⊕\oplus 表示按位异或。

输入格式

第一行包含六个整数 n,m,x,a,b,cn,m,x,a,b,c。

第二行一个长度为 2m−12m-1 的字符串 isGood。

输出格式

输出一个整数,表示上述异或值。

数据范围

  • 2≤n,m≤5002\le n,m\le 500;
  • 0≤x,a,b,c≤1090\le x,a,b,c\le 10^9;
  • isGood 长度恰为 2m−12m-1,且只包含 Y 和 N。

样例

输入

2 4 1 1 0 0
NNYYNYN

输出

9