Cantor

#include <bits/stdc++.h>
#define MAX 107

using namespace std;
typedef long long ll;

ll bit[MAX],C[11], base;
map<ll, ll> dp[MAX];
ll dfs(int pos, int val, int flag, int ini){
    //if(pos == 0 ) cout << rep << endl;
    if(pos == 0) return val != 0;
    if(!flag && dp[pos].count(val)) return dp[pos][val];

    ll ans = 0;

    int end = flag? bit[pos]: (base-1);
    for(int i = 0; i <= end; i++){
        if(!C[i] && i == 0 && ini) ans = ans + dfs(pos-1, val+i, flag && i == end, true);
        if(!C[i]) continue;
        ans = ans + dfs(pos-1, val+i, flag && i == end, false);
    }
    if(!flag) dp[pos][val] = ans;
    return ans;
}

bool check(ll a){
    int len = 0;
    while(a){
        bit[++len] = a%base;
        a /= base;
    }

    for(int i = 1; i <= len; i++){
        if(!C[i]) return false;
    }
    return true;
}
ll solve(ll a){
    int len = 0;
    while(a){
        bit[++len] = a%base;
        a /= base;
    }

    return dfs(len, 0, true, true);
}
int main(){
    while(true){
        for(int i = 0; i < MAX; i++) dp[i].clear();
        string conjunto;
        ll a, b; cin >> a >> b >> base >> conjunto;
        if( a+b+base == -3) break;
        for(int i = 0; i < conjunto.size(); i++){
            if(conjunto[i] == 'S') C[i] = true;
            else C[i] = false;
        }
        cout << solve(b)-solve(a)+check(a) << endl;
    }
    return 0;
}