#arc157c. [arc157_c]YY Square

[arc157_c]YY Square

给定 H×WH \times W 的矩阵,每个位置上有一个字符,是 XY

定义一条路径的权值为,将其经过的字符按顺序拼接成一个字符串,YY 在这个字符串的出现次数。

要求每次只能向右或向下走,求,所有的 (H+W2H1)\binom{H + W - 2}{H - 1} 条左上到右下的路径,它们权值平方的和。