import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

public class Euler674 {
    static final long MOD = 1000000000L;

    enum NodeType {
        VARIABLE, I_OP
    }

    static abstract class Node {
        NodeType type;
    }

    static class VarNode extends Node {
        String name;

        VarNode(String name) {
            this.type = NodeType.VARIABLE;
            this.name = name;
        }
    }

    static class INode extends Node {
        Node left, right;

        INode(Node left, Node right) {
            this.type = NodeType.I_OP;
            this.left = left;
            this.right = right;
        }
    }

    static String serialize(Node n) {
        if (n.type == NodeType.VARIABLE) {
            return ((VarNode) n).name;
        }
        INode i = (INode) n;
        return "I(" + serialize(i.left) + "," + serialize(i.right) + ")";
    }

    static class Parser {
        String s;
        int pos;

        Parser(String s) {
            this.s = s;
            this.pos = 0;
        }

        void skip() {
            while (pos < s.length() && Character.isWhitespace(s.charAt(pos))) {
                pos++;
            }
        }

        boolean consume(char c) {
            skip();
            if (pos < s.length() && s.charAt(pos) == c) {
                pos++;
                return true;
            }
            return false;
        }

        boolean matchString(String str) {
            skip();
            if (s.startsWith(str, pos)) {
                pos += str.length();
                return true;
            }
            return false;
        }

        Node parseTerm() {
            if (matchString("I(") || matchString("J(")) {
                Node left = parseTerm();
                consume(',');
                Node right = parseTerm();
                consume(')');
                return new INode(left, right);
            } else {
                skip();
                int start = pos;
                while (pos < s.length() && (Character.isLetterOrDigit(s.charAt(pos)) || s.charAt(pos) == '_')) {
                    pos++;
                }
                return new VarNode(s.substring(start, pos));
            }
        }

        boolean hasMore() {
            skip();
            return pos < s.length();
        }
    }

    static Node resolve(Node node, Map<String, Node> bindings) {
        if (node.type == NodeType.VARIABLE) {
            VarNode v = (VarNode) node;
            if (bindings.containsKey(v.name)) {
                return resolve(bindings.get(v.name), bindings);
            }
        }
        return node;
    }

    static boolean occurs(String varName, Node term, Map<String, Node> bindings, Set<Node> visited) {
        Node r = resolve(term, bindings);
        if (!visited.add(r))
            return false;

        if (r.type == NodeType.VARIABLE) {
            return ((VarNode) r).name.equals(varName);
        } else {
            INode i = (INode) r;
            return occurs(varName, i.left, bindings, visited) || occurs(varName, i.right, bindings, visited);
        }
    }

    static boolean unify(Node t1, Node t2, Map<String, Node> bindings) {
        Node r1 = resolve(t1, bindings);
        Node r2 = resolve(t2, bindings);

        if (r1 == r2)
            return true;

        if (r1.type == NodeType.VARIABLE) {
            VarNode v1 = (VarNode) r1;
            if (r2.type == NodeType.VARIABLE && ((VarNode) r2).name.equals(v1.name))
                return true;
            Set<Node> visited = new HashSet<>();
            if (occurs(v1.name, r2, bindings, visited))
                return false;
            bindings.put(v1.name, r2);
            return true;
        }

        if (r2.type == NodeType.VARIABLE) {
            VarNode v2 = (VarNode) r2;
            Set<Node> visited = new HashSet<>();
            if (occurs(v2.name, r1, bindings, visited))
                return false;
            bindings.put(v2.name, r1);
            return true;
        }

        if (r1.type == NodeType.I_OP && r2.type == NodeType.I_OP) {
            INode i1 = (INode) r1;
            INode i2 = (INode) r2;
            return unify(i1.left, i2.left, bindings) && unify(i1.right, i2.right, bindings);
        }

        return false;
    }

    static long evalJ(long x, long y) {
        long sum = (1 + x + y) % MOD;
        long term1 = (sum * sum) % MOD;
        long diff = (y - x) % MOD;
        long res = (term1 + diff) % MOD;
        if (res < 0)
            res += MOD;
        return res;
    }

    static long evaluate(Node node, Map<String, Node> bindings, Map<Node, Long> cache) {
        Node r = resolve(node, bindings);
        if (cache.containsKey(r))
            return cache.get(r);

        long res;
        if (r.type == NodeType.VARIABLE) {
            res = 0;
        } else {
            INode i = (INode) r;
            long lv = evaluate(i.left, bindings, cache);
            long rv = evaluate(i.right, bindings, cache);
            res = evalJ(lv, rv);
        }
        cache.put(r, res);
        return res;
    }

    static long solvePair(Node e1, Node e2) {
        Map<String, Node> bindings = new HashMap<>();
        if (unify(e1, e2, bindings)) {
            return evaluate(e1, bindings, new IdentityHashMap<>());
        }
        return 0;
    }

    public static String solve() {
        String content = "";
        String[] paths = { "I-expressions.txt", "solutionsCpp/I-expressions.txt", "../I-expressions.txt" };
        for (String path : paths) {
            try {
                content = new String(Files.readAllBytes(Paths.get(path)));
                break;
            } catch (IOException ignored) {
            }
        }
        if (content.isEmpty())
            return "File not found";

        Parser parser = new Parser(content);
        List<Node> fileExprs = new ArrayList<>();
        while (parser.hasMore()) {
            fileExprs.add(parser.parseTerm());
        }

        Map<String, Integer> strToId = new HashMap<>();
        List<Node> uniqueExprs = new ArrayList<>();
        List<Integer> fileIds = new ArrayList<>();

        for (Node e : fileExprs) {
            String s = serialize(e);
            if (!strToId.containsKey(s)) {
                strToId.put(s, uniqueExprs.size());
                uniqueExprs.add(e);
            }
            fileIds.add(strToId.get(s));
        }

        int nUnique = uniqueExprs.size();
        long[] pairCache = new long[nUnique * nUnique];

        for (int i = 0; i < nUnique; ++i) {
            for (int j = i; j < nUnique; ++j) {
                long val = solvePair(uniqueExprs.get(i), uniqueExprs.get(j));
                pairCache[i * nUnique + j] = val;
                pairCache[j * nUnique + i] = val;
            }
        }

        long totalSum = 0;
        int totalExprs = fileExprs.size();
        for (int i = 0; i < totalExprs; ++i) {
            for (int j = i + 1; j < totalExprs; ++j) {
                int id1 = fileIds.get(i);
                int id2 = fileIds.get(j);
                if (id1 == id2)
                    continue;
                totalSum = (totalSum + pairCache[id1 * nUnique + id2]) % MOD;
            }
        }

        return Long.toString(totalSum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}