The perfect base

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define _ << " , " <<
#define ii pair<int, int>
#define fi first
#define se second
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int ms = 1011000;

int pt;
string s;
int F[ms];
bitset<ms> composite;

char read() {
    if(pt >= SZ(s)) return '.';
    return s[pt];
}

int read_next_integer() {
    int x = 0;
    while(read() >= '0' and read() <= '9') {
        int d = read() - '0';
        x = 10 * x + d;
        pt++;
    }
    return x;
}

void sieve() {
    for(int i = 2; i < ms; ++i)
        if(!composite[i])
            for(int j = i; j < ms; j += i)
                if(F[j] == 0)
                    F[j] = i;
}

map<int, int> factorization(int x) {
    map<int, int> f;
    while(x > 1) {
        f[F[x]]++;
        x /= F[x];
    }
    return f;
}

void solve(){
    sieve();

    cin >> s;

    map<int, int> prime_frequency;

    auto compute = [&](int x, int v) {
        auto f = factorization(x);
        for(auto it : f)
            prime_frequency[it.fi] += v * it.se;
    };

    map<int, int> factorials;
    int cnt_factorials = 0;

    while(pt < SZ(s)) {
        int x = read_next_integer();
        if(read() == '!') {
            pt++;
            int e = 1;
            if(read() == '^') {
                pt++;
                int a = read_next_integer();
                if(read() == '!') {
                    if(a > 1) e = 0;
                    pt++;
                }
                e = (e * a) % 2;
            }
            while(read() == '^') {
                pt++;
                int a = read_next_integer();
                if(read() == '!') pt++;
            }
            if(e & 1) factorials[x]++, cnt_factorials++;
            pt++;
        } else if(read() == '^') {
            pt++;
            int a = read_next_integer(), e = 1;
            if(read() == '!') {
                if(a > 1) e = 0;
                pt++;
            }
            e = (e * a) % 2;
            while(read() == '^') {
                pt++;
                int a = read_next_integer();
                if(read() == '!') pt++;
            }
            if(e & 1) compute(x, 1);
        } else {
            compute(x, 1);
            pt++;
        }
    }

    int cnt = SZ(factorials);

    int number = 1;
    for(auto it : factorials) {
        int cur = it.fi;
        while(number <= cur) compute(number, cnt_factorials), number++;
        cnt_factorials -= it.se;
    }

    bool flag = true;
    for(auto it : prime_frequency)
        if(it.se & 1)
            flag = false;

    if(flag) cout << "S\n";
    else cout << "N\n";
}

int32_t main() {
    fastio;
    solve();
    return 0;
}