สวนหลวงสมดุล: เงื่อนไขที่พูดถึงทุกช่วง ยุบเหลือรางกว้างสองหน่วย

// เฉลยชุดทดสอบย่อย N ไม่เกิน 40 (40 คะแนน)
// ยังไม่ต้องมองออกว่าสถานะบีบเหลือหกแบบ แค่จำสถานะดิบ ๆ ไว้ใน map ก็พอ
// เพราะเงื่อนไขสมดุลบังคับให้ค่ามากสุดลบค่าน้อยสุดไม่เกินสอง สถานะที่ไปถึงได้จึงมีไม่กี่อัน
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N; ll MOD;
map<array<int,4>, ll> memo;                         // (ตำแหน่ง, ผลรวมสะสม, ค่าน้อยสุด, ค่ามากสุด)

ll ways(int i, int s, int mn, int mx) {
    if (mx - mn > 2) return 0;
    if (i == N) return 1;
    array<int,4> key{i, s, mn, mx};
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;
    ll v = 0;
    for (int d = 1; d >= -1; d -= 2) {               // +1 คือปลูกบัว, -1 คือปลูกกก
        int ns = s + d;
        v += ways(i + 1, ns, min(mn, ns), max(mx, ns));
    }
    return memo[key] = v;
}

int main() {
    scanf("%d %lld", &N, &MOD);
    char buf[64]; scanf("%s", buf); string g = buf;
    ll rank_ = 1;
    int s = 0, mn = 0, mx = 0;
    for (int i = 0; i < N; i++) {
        if (g[i] == 'P') {                           // ต้นบัวมาก่อนต้นกกตามพจนานุกรม
            int ns = s + 1;
            rank_ += ways(i + 1, ns, min(mn, ns), max(mx, ns));
        }
        s += (g[i] == 'L' ? 1 : -1);
        mn = min(mn, s); mx = max(mx, s);
    }
    printf("%lld\n", rank_ % MOD);
}

#include <bits/stdc++.h>
using namespace std;
// state = (a,b): a = S - minS, b = maxS - minS, 0<=a<=b<=2  -> 6 states
static int SID[3][3]; static int SA[6],SB[6],NS;
static inline int stepState(int s,int c){ // c=0 -> 'L'(+1), c=1 -> 'P'(-1); -1 = invalid
    int a=SA[s],b=SB[s];
    if(c==0){ int na=a+1,nb=b; if(na>nb) nb=na; if(nb>2) return -1; return SID[na][nb]; }
    int na=a-1,nb=b; if(na<0){ na=0; nb=b+1; } if(nb>2) return -1; return SID[na][nb];
}
int main(){
    long long N,M; if(scanf("%lld %lld",&N,&M)!=2) return 0;
    static char buf[1000006]; scanf("%s",buf); string s=buf;
    NS=0; for(int b=0;b<=2;b++) for(int a=0;a<=b;a++){ SID[a][b]=NS; SA[NS]=a; SB[NS]=b; NS++; }
    int n=(int)N;
    vector<array<long long,6>> g(n+1);
    for(int t=0;t<6;t++) g[n][t]=1%M;
    for(int i=n-1;i>=0;i--) for(int t=0;t<6;t++){
        long long v=0;
        for(int c=0;c<2;c++){ int nx=stepState(t,c); if(nx>=0) v+=g[i+1][nx]; }
        g[i][t]=v%M;
    }
    long long rank_=1%M; int cur=SID[0][0];
    for(int i=0;i<n;i++){
        if(s[i]=='P'){ int nx=stepState(cur,0); if(nx>=0) rank_=(rank_+g[i+1][nx])%M; }
        cur=stepState(cur,s[i]=='L'?0:1);
        if(cur<0){ printf("-1\n"); return 0; }
    }
    printf("%lld\n",rank_%M);
}