<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

365. Ships of the Desert
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



During one of his trips Vasya went to Egypt. He needed to cross the desert. This is pretty easy to do because of caravans furrowing the desert. The only thing Vasya needed was to buy a ticket. Inhabitants told Vasya that he should buy peculiar ticket to get a lot of luck in his life. Vasya found out that peculiar ticket is so-called ticket-dromedary (named after the dromedary camels that are crossing the desert). Ticket can be called dromedary if digits in its number are going in non-descending order and then in non-ascending order (length of any digit group may equals to zero). Vasya has interesting question: how many tickets-dromedaries exist with number consisting of exactly S digits?

Input
The first line of the input file contains S (1 ≤ S ≤ 20) — amount of digits in the ticket number. Ticket number may have leading zeroes.

Output
Print amount of tickets-dromedaries with exactly S digits.

Example(s)
sample input
sample output
1
10

sample input
sample output
3
715

<|response|>
1) Abridged problem statement
- Count the number of sequences of length S (1 ≤ S ≤ 20) over digits 0..9 (leading zeros allowed) whose digits first go in non-decreasing order and then in non-increasing order. Either part may be empty. Print the count.

2) Key observations
- A valid sequence is unimodal with at most one “turn” (up, then down), equal digits allowed anywhere.
- Allowing empty parts means:
  - Entire sequence may be non-decreasing, or non-increasing, or even constant; all are valid.
- A clean digit DP exists:
  - State by (position, phase, last_digit), where phase=0 means still going up, phase=1 means going down.
  - Transition:
    - Up: choose next digit d ≥ last to stay up; choose next digit d < last to switch to down.
    - Down: choose next digit d ≤ last to stay down.
  - Start with last=0 because leading zeros are allowed.
- Each unimodal sequence is counted exactly once: the DP switches to “down” only at the first strict decrease and never switches back.
- Results fit in 64-bit integers.
- There is also a closed-form combinatorial formula:
  - Let m be the maximum digit (0..9) and choose the last occurrence of m as the pivot.
  - Count how many digits of 0..m-1 go to the left (non-decreasing side), how many extra m’s go to the left (beyond the pivot), and how many 0..m-1 go to the right (non-increasing side). That’s 2m+1 nonnegative variables summing to S−1.
  - Number of solutions: C(S + 2m − 1, 2m).
  - Total answer: sum over m=0..9 of C(S + 2m − 1, 2m).

3) Full solution approach
- We use digit DP with memoization.
  - State dp[pos][phase][last]:
    - pos: how many digits have been placed (0..S).
    - phase: 0 = still in the non-decreasing phase, 1 = already in the non-increasing phase.
    - last: last placed digit (0..9).
  - Base case: if pos == S, return 1 (one valid sequence completed).
  - Transitions:
    - If phase == 0:
      - For d in [last..9]: continue in phase 0.
      - For d in [0..last-1]: switch to phase 1.
    - If phase == 1:
      - For d in [0..last]: remain in phase 1.
  - Initialization: call rec(0, 0, 0). Leading zeros are allowed, so this enumerates all valid sequences.
- Correctness:
  - Every valid unimodal sequence has exactly one earliest position where a strict decrease first happens (or never happens if entirely non-decreasing). The DP mirrors this event by switching phase only on a strict decrease, hence no double counting and no omission.
- Complexity:
  - States: S * 2 * 10 ≤ 20 * 2 * 10 = 400.
  - Each state transitions to at most 10 next digits.
  - Total work is O(S * 10 * 10) ≈ a few thousand operations; memory is tiny.
- Optional closed form:
  - Answer = sum_{m=0}^{9} C(S + 2m − 1, 2m). With S ≤ 20, all values fit into 64-bit integers. This is even faster to implement.

4) C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int S;

void read() { cin >> S; }

vector<vector<vector<int64_t>>> dp;

int64_t rec(int pos, int state, int last_digit) {
    if(pos == S) {
        return 1;
    }

    int64_t& memo = dp[pos][state][last_digit];
    if(memo != -1) {
        return memo;
    }

    memo = 0;

    if(state == 0) {
        for(int d = last_digit; d <= 9; d++) {
            memo += rec(pos + 1, 0, d);
        }
        for(int d = 0; d < last_digit; d++) {
            memo += rec(pos + 1, 1, d);
        }
    } else {
        for(int d = 0; d <= last_digit; d++) {
            memo += rec(pos + 1, 1, d);
        }
    }

    return memo;
}

void solve() {
    // This is a classical problem on digit DP. The state we want to keep is:
    //    dp[pos][state][last_digit].
    //        - pos is the position, starting from S - 1.
    //        - state = 0 means that we are building the increasing prefix,
    //          while state = 1 means that we are building the decreasing. We
    //          start from 0 state.
    //        - last_digit is the last digit we placed (0 at the beginning).

    dp.assign(S, vector<vector<int64_t>>(2, vector<int64_t>(10, -1)));
    cout << rec(0, 0, 0) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5) Python implementation with detailed comments
```python
import sys
from functools import lru_cache

def solve_dp(S: int) -> int:
    # Digit DP with memoization.
    # State:
    #   pos   : how many digits have been placed (0..S)
    #   phase : 0 = non-decreasing so far, 1 = now non-increasing
    #   last  : last digit placed (0..9)
    @lru_cache(maxsize=None)
    def rec(pos: int, phase: int, last: int) -> int:
        if pos == S:
            return 1  # one valid sequence completed

        total = 0
        if phase == 0:
            # Stay "up" with d >= last
            for d in range(last, 10):
                total += rec(pos + 1, 0, d)
            # Switch to "down" with d < last
            for d in range(0, last):
                total += rec(pos + 1, 1, d)
        else:
            # Already "down": must keep non-increasing d <= last
            for d in range(0, last + 1):
                total += rec(pos + 1, 1, d)
        return total

    return rec(0, 0, 0)

def solve_formula(S: int) -> int:
    # Closed form: sum_{m=0}^9 C(S + 2m - 1, 2m)
    # Use a small Pascal triangle since S <= 20 -> n <= 37.
    N = S + 17
    C = [[0] * (N + 1) for _ in range(N + 1)]
    for n in range(N + 1):
        C[n][0] = C[n][n] = 1
        for k in range(1, n):
            C[n][k] = C[n-1][k-1] + C[n-1][k]

    ans = 0
    for m in range(10):
        n = S + 2*m - 1
        k = 2*m
        ans += C[n][k]
    return ans

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    S = int(data[0])

    # Either method is fine; both are extremely fast for S <= 20.
    # ans = solve_formula(S)
    ans = solve_dp(S)

    print(ans)

if __name__ == "__main__":
    main()
```
