#include <bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) using namespace std; int pos[1000005][4][4],n,m; string s; signed main(void) { exoworldgd; cin >> n >> m >> s; for (int i = n; i >= 0; --i){ for(int mx = 0; mx <= 2; mx++){ for(int mn = 0; mn <= 2; mn++){ if(i == n){pos[i][mx][mn] = 1; continue;} pos[i][mx][mn]=pos[i+1][mx+1][max(0,mn-1)]+pos[i+1][max(0,mx-1)][mn+1],pos[i][mx][mn]-=pos[i][mx][mn]>=m?m:0; } } } int rank=0,mx=0,mn=0; for(int i = 0; i < n; i++){ if (s[i] == 'L') {mx = max(0,mx-1), mn++; continue;} rank += pos[i+1][max(0,mx-1)][mn+1], rank -= rank >= m ? m : 0, mx++, mn = max(0,mn-1); } rank++, cout << rank - (rank >= m ? m : 0); }