#include <iostream>
#include <vector>

using namespace std;

#define SUBSTR_SZ 3 // Substring size

class Stack{
private:
    vector<string> _stack_vec;
    int 	    _top;

public:
    Stack(){        
        _top = -1;
    }
    void pop(){
        if(!is_empty()) {
            _top = _top - 1;
            _stack_vec.pop_back();
            return;
        } else {
            std::cout << "Could not retrieve data, stack is empty\n";
        }
        return;
    }
    void push(string _str){
        _top += 1;   
        _stack_vec.push_back(_str);
    }

    string get_top() {
        return _stack_vec[_top];
    }
    int is_empty(){
        return !_stack_vec.size();
    }

    int stack_size() {
        return _top + 1;
    }
};

int main() {
    Stack stack;
    // string _str = "tactactictactictictac"; // valid
    string _str = "tactictac"; // invalid

    // first to label whether the first tic is met
    bool valid = true, first = false;

    for (int i = 0; i < _str.size(); i = i+SUBSTR_SZ) {
        string _substr = _str.substr(i, SUBSTR_SZ);
        if (i == 0 && _substr == "tic") {
            valid = false;
            break;
        }
        if (stack.is_empty() && _substr == "tac") {
            stack.push(_substr);
            continue;
        }

        if(!stack.is_empty()) {
            if (_substr == "tac") stack.push(_substr);
            else {
                if (stack.get_top() == "tic") {
                    valid = false;
                    break;
                } else {
                    // When not meeting the first tac, with current
                    // top is "tac", pop it out
                    if (!first) {
                        stack.pop();
                        // The first tic is met: tac tac tic
                        if (!stack.is_empty() && stack.get_top() == "tac") {
                            first = true;
                            stack.pop();
                            continue;
                        } else valid = false;
                    }
                    else stack.push(_substr);
                }
            }
        }
    }

    std::cout << valid << "\n";

   	return 0;
}