#P17724. [2026年福建省队集训]猜拳机

[2026年福建省队集训]猜拳机

题目描述

把一串由 R(石头)、S(剪刀)、P(布)组成的字符串扔进"猜拳机"里。

让相邻的两个手势猜拳,谁赢了就留下谁;平局留下自己。一次操作后字符串第 ii 个位置为原字符串第 ii 和第 i+1i+1 个位置的没输的手势,长度减一。

有一个未知字符串 SS,被猜拳机操作了 kk 次得到了字符串 TT。

求有多少不同的 SS 满足条件?答案对 998244353998244353 取模。

输入格式

第一行一个字符串 TT,由 R、S、P 构成。

第二行一个正整数 kk,表示操作次数。

输出格式

一行一个整数,表示答案。

样例

样例 1

输入:

SSRP
1

输出:

3

样例 2

输入:

SSPPP
3

输出:

88

数据范围与约定

对于 100%100\% 的数据,1≤∣T∣,k≤30001 \le |T|, k \le 3000。

子任务

  • Subtask 1(10 分):k=1k = 1
  • Subtask 2(20 分):k≤5k \le 5
  • Subtask 3(10 分):∣T∣+k≤15|T| + k \le 15
  • Subtask 4(30 分):∣T∣,k≤100|T|, k \le 100
  • Subtask 5(30 分):无特殊限制