#include <string>
using namespace std;

/**
 * Given a street number and an avenue number, returns the number of
 * paths Karel has from that location back to the origin at 1st Street
 * and 1st Avenue, assuming Karel only moves left and down.
 * <p>
 * Notice that the coordinates here are 1-indexed.
 *
 * @param street Karel's starting street number.
 * @param avenue Karel's starting avenue number.
 * @return The number of paths back to (1, 1) moving only left and down.
 */
int numPathsHome(int street, int avenue) {
    /* If Karel is at position (1, 1), there is one path back: just don't move anywhere! */
    if (street == 1 && avenue == 1) return 1;
    
    /* If Karel is at a street or avenue numbered less than one, then just by moving left
     * or down there's no way to get to (1, 1).
     */
    if (street <= 0 || avenue <= 0) return 0;
    
    /* Otherwise, every journey begins with a single step! Count how many ways we can go
     * home starting with a left step and hwo many ways we can go home starting with a
     * down step.
     */
    return numPathsHome(street - 1, avenue) + numPathsHome(street, avenue - 1);
}

/**
 * Given two strings, returns whether the second is a subsequence of
 * the first.
 *
 * @param text The larger text.
 * @param subseq The subsequence to search for.
 * @return Whether text has subseq as a subsequence.
 */
bool hasSubsequence(const string& text, const string& subseq) {
    /* The empty string is a subsequence of any text string. */
    if (subseq == "") return true;
    
    /* If the sequence is nonempty but the text is empty, then the sequence isn't a
     * subsequence of the text.
     */
    if (text == "") return false;
    
    /* If the first characters of the text and subsequence match, then peel both off
     * and see whether the remaining sequence is a subsequence of the remaining text.
     */
    if (text[0] == subseq[0]) return hasSubsequence(text.substr(1), subseq.substr(1));
    
    /* Otherwise, they don't match. Then the sequence is a subsequence precisely if
     * it's a subsequence of the rest of the text.
     */
    return hasSubsequence(text.substr(1), subseq);
}