class Solution {
public:
    vector<int> getNext(string pattern) {
        int len = (int)pattern.length();
        vector<int> res(len+1,0);
        int j = 0;
        for (int i = 1 ; i < len ; i++) {
            while (j && pattern[i] != pattern[j])   j = res[j];
            if (pattern[i] == pattern[j])   j++;
            res[i+1] = j;
        }
        return res;
    }

    int searchPosition(string text, string pattern, vector<int>& next) {
        int j = 0 , lt = (int)text.length() , lp = (int)pattern.length();
        for (int i = 0 ; i < lt ; i++) {
            while (j && text[i] != pattern[j])  j = next[j];
            if (text[i] == pattern[j])  j++;
            if (j == lp)    return i-j+1;
        }
        return -1;
    }
    bool isSubstr(string pattern, string text, unordered_map<string, vector<int>>& nextmp) {
        if (searchPosition(text, pattern, nextmp[pattern]) >= 0)    return true;
        else    return false;
    }
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });
        unordered_map<string, vector<int>> nextmp;
        for (auto str : words) {
            nextmp[str] = getNext(str);
        }
        int n = words.size();
        vector<string> ans;
        unordered_map<string, bool> vis;
        for (int i = 0 ; i < n ; i++) {
            for (int j = i+1 ; j < n ; j++) {
                if (!vis[words[i]] && isSubstr(words[i], words[j], nextmp)) {
                    ans.push_back(words[i]);
                    vis[words[i]] = true;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> p = vector<int>(m, 0);
        for (int i = 0 ; i < m ; i++) {
            p[i] = i + 1;
        }
        vector<int> ans;
        for (auto q : queries) {
            for (int i = 0 ; i < m ; i++) {
                if (q == p[i]) {
                    ans.push_back(i);
                    for (int j = i ; j >= 1 ; j--) {
                        p[j] = p[j-1];
                    }
                    p[0] = q;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    string entityParser(string text) {
        int len = text.length();
        string ans = "";
        for (int i = 0 ; i < len ; ) {
            if (text[i] == ‘&‘) {
                if (text[i+1] == ‘q‘ && text[i+2] == ‘u‘ && text[i+3] == ‘o‘ && text[i+4] == ‘t‘ && text[i+5] == ‘;‘) {
                    ans += ‘"‘;
                    i += 6;
                } else if (text[i+1] == ‘a‘ && text[i+2] == ‘p‘ && text[i+3] == ‘o‘ && text[i+4] == ‘s‘ && text[i+5] == ‘;‘) {
                    ans += ‘\‘‘;
                    i += 6;
                } else if (text[i+1] == ‘a‘ && text[i+2] == ‘m‘ && text[i+3] == ‘p‘ && text[i+4] == ‘;‘) {
                    ans += ‘&‘;
                    i += 5;
                } else if (text[i+1] == ‘g‘ && text[i+2] == ‘t‘ && text[i+3] == ‘;‘) {
                    ans += ‘>‘;
                    i += 4;
                } else if (text[i+1] == ‘l‘ && text[i+2] == ‘t‘ && text[i+3] == ‘;‘) {
                    ans += ‘<‘;
                    i += 4;
                } else if (text[i+1] == ‘f‘ && text[i+2] == ‘r‘ && text[i+3] == ‘a‘ && text[i+4] == ‘s‘ && text[i+5] == ‘l‘ && text[i+6] == ‘;‘) {
                    ans += ‘/‘;
                    i += 7;
                } else {
                    ans += ‘&‘;
                    i++;
                }
            } else {
                ans += text[i];
                i++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int numOfWays(int n) {
        long long mod = 1000000007;
        vector<long long> dp1 = vector<long long>(n, (long long)1);
        vector<long long> dp2 = vector<long long>(n, (long long)1);
        for (int i = 1 ; i < n ; i++) {
            dp1[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)2) % mod;
            dp2[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)3) % mod;
        }
        long long ans = (long long)6 * (dp1[n-1] + dp2[n-1]) % mod;
        return (int)ans;
    }
};