class Solution {
public:
    bool isNumber(char ch) {
        return ch >= ‘0‘ && ch <= ‘9‘;
    }
    string reformat(string s) {
        char mark = s[0];
        int len = s.length(), i = 0, j = len - 1;
        while (i < j) {
            while (i < j && (isNumber(mark) != isNumber(s[j]))) j--;
            while (i < j && (isNumber(mark) == isNumber(s[i]))) i++;
            swap(s[i], s[j]);
        }
        if (abs(len - i - 1 - i - 1) > 1)   return "";
        // cout << i+1 << " " << len - i -1 << endl;
        string ans = "";
        if (len - i - 1 > i + 1) {
            ans += s[len-1];
            for (int p = 0 ; p <= i ; p++) {
                ans += s[p];
                ans += s[p+i+1];
            }
        } else if (len - i - 1 < i + 1) {
            for (int p = 0 ; p < i ; p++) {
                ans += s[p];
                ans += s[p+i+1];
            }
            ans += s[i];
        } else {
            for (int p = 0 ; p <= i ; p++) {
                ans += s[p];
                ans += s[p+i+1];
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        sort(orders.begin(), orders.end(), [](vector<string>& a, vector<string>& b) {
            return a[1] < b[1];
        });
        map<int, map<string, int>> tables;
        map<string, bool> foods;
        for (auto o : orders) {
            for (int i = 2 ; i < o.size() ; i++) {
                int table = atoi(o[1].c_str());
                if (tables.find(table) == tables.end()) {
                    tables[table] = map<string, int>();
                }
                if (tables[table].find(o[i]) == tables[table].end()) {
                    tables[table][o[i]] = 0;
                }
                tables[table][o[i]]++;
                foods[o[i]] = true;
                // cout << o[i] << endl;
            }
        }
        // cout << tables.size() << endl;
        vector<vector<string>> ans = vector<vector<string>>(tables.size()+1, vector<string>());
        ans[0].push_back("Table");
        for (auto it : foods) {
            ans[0].push_back(it.first);
        }
        int i = 1;
        for (auto it : tables) {
            ans[i++].push_back(to_string(it.first));
            for (auto food : foods) {
                if (it.second.find(food.first) == it.second.end()) {
                    it.second[food.first] = 0;
                }
                ans[i-1].push_back(to_string(it.second[food.first]));
            }
        }
        return ans;
    }
};

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<char, int> cnt;
        cnt[‘c‘] = cnt[‘r‘] = cnt[‘o‘] = cnt[‘a‘] = cnt[‘k‘];
        int len = croakOfFrogs.length(), ans = 0;
        for (int i = 0 ; i < len ; i++) {
            char cur = croakOfFrogs[i];
            cnt[cur]++;
            if (cur == ‘c‘) {
                if (cnt[‘k‘])   cnt[‘k‘]--;
                else    ans++;
            } else if (cur == ‘r‘) {
                cnt[‘c‘]--;
            } else if (cur == ‘o‘) {
                cnt[‘r‘]--;
            } else if (cur == ‘a‘) {
                cnt[‘o‘]--;
            } else if (cur == ‘k‘) {
                cnt[‘a‘]--;
            }
            if (cnt[‘a‘] < 0 || cnt[‘r‘] < 0 || cnt[‘o‘] < 0 || cnt[‘a‘] < 0)   break;
        }
        if (cnt[‘a‘] != 0 || cnt[‘r‘] != 0 || cnt[‘o‘] != 0 || cnt[‘a‘] != 0)   return -1;
        return ans;
    }
};

class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        long long mod = (long long)1000000007;
        vector<vector<vector<long long>>> dp = vector<vector<vector<long long>>>(n+1, vector<vector<long long>>(m+1, vector<long long>(k+2, (long long)0)));
        for (int i = 1 ; i <= m ; i++) {
            dp[1][i][1] = (long long)1;
        }
        for (int i = 1 ; i < n ; i++) {
            for (int j = 1 ; j <= m ; j++) {
                for (int l = 1 ; l <= k ; l++) {
                    for (int r = 1 ; r <= m ; r++) {
                        if (r > j) {
                            dp[i+1][r][l+1] += dp[i][j][l];
                            dp[i+1][r][l+1] %= mod;
                        } else {
                            dp[i+1][j][l] += dp[i][j][l];
                            dp[i+1][j][l] %= mod;
                        }
                    }
                }
            }
        }
        long long ans = (long long)0;
        for (int i = 1 ; i <= m ; i++) {
            ans += dp[n][i][k];
            ans %= mod;
        }
        return (int)ans;
    }
};