Spionul 008 vrea să găsească o locație secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi cu fiecare pas, el avansează de la nivelul i la nivelul i+1, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia u faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V), trecând de pe nivelul i pe nivelul i+1 cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caracterele E sau V, corespunzătoare deplasării spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4 a nivelului 6.

Cerinţă

Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:

Spionul 008 vrea să găsească o locație secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi cu fiecare pas, el avansează de la nivelul i la nivelul i+1, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia u faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V), trecând de pe nivelul i pe nivelul i+1 cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caracterele E sau V, corespunzătoare deplasării spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4 a nivelului 6.

Cerinţă

Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:
a) poziţia locației secrete de pe ultimul nivel;
b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia inițială pentru a ajunge în locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o poziţie.

Date de intrare

Fișierul de intrare spion1.in conține pe prima linie un număr natural pdin {1,2}, iar pe a doua linie o succesiune de caractere corespunzătoare unui traseu.

Date de ieșire

Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerință. În acest caz, fişierul de ieşire spion1.out va conţine pe prima linie un număr natural ce reprezintă poziția de pe nivelul final a locației secrete.

Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerință. În acest caz, fişierul de ieşire spion1.out va conţine pe prima linie un număr natural ce reprezintă numărul de trasee distincte modulo 100 003.

Restricții și precizări

• 2 ≤ lungimea şirului paşilor ≤ 100 000;
• pentru 20% din teste valoarea lui p=1;
• pentru alte 10% din teste valoarea lui p=2 şi lungimea secvenţei de caractere ≤ 255;
• pentru alte 10% din teste valoarea lui p=2 şi 300 ≤ lungimea secvenţei de caractere ≤ 1900;
• pentru alte 10% din teste valoarea lui p=2 şi 3000 ≤ lungimea secvenţei de caractere ≤ 5000.

1
VEEVE

4

2
VEV

3

2
EVEVVEVEEE

210

#include <bits/stdc++.h>

using namespace std;

ifstream cin("spion1.in");
ofstream cout("spion1.out");

#define mod 100003

int E[1000001];
int C[100001];

void ciur(int E[] , int n)
{
    for(int i = 2 ; i <= n ; i++) E[i] = 1;
    for(int i = 2 ; i * i <= n ; i++)
        if(E[i] == 1)
            for(int j = i*i ; j <= n ; j += i) E[j] = 0;

}

int np(int n , int x)
{
    ///la ce putere apare x in n faactorial
    int p = x , val = 0;
    while(n >= p)
    {
        val += n / p;
        p *= x;
    }
    return val;
}

unsigned long long xlan(int x , int n)
{
    if(n == 0) return 1;
    else
    {
        unsigned long long p = xlan(x , n / 2);
        if(n % 2 == 0) p = p * p % mod;
        else p = p * p * x % mod;
        return p;
    }
}
int main()
{
    int cer;
    char s[100001];
    ciur(E , 100001);
    cin >> cer >> s;
    int i = 0 , cnt = 0 , n = strlen(s);
    while(s[i] != '\0')
    {
        if(s[i] == 'E') cnt++;
        i++;
    }
    if(cer == 1) cout << cnt + 1;
    else
    {
        unsigned long long k = 1;
        for(int i = 2 ; i <= n ; i++)
            if(E[i]) C[i] = np(n , i);
        for(int i = 2 ; i <= cnt ; i++)
            if(E[i]) C[i] -= np(cnt , i);
        for(int i = 2 ; i <= n - cnt ; i++)
            if(E[i]) C[i] -= np(n - cnt , i);
        for(int i = 2 ; i <= n; i++)
            k = k * xlan(i , C[i]) % mod;
        cout << k;
    }

}