Under construction

Still being built. Things may change

Ascending Numbers

Interview

Time limit1sMemory limit256 MB

Summary
Count length-N digit strings, leading zeros allowed, whose digits never decrease left to right, modulo 10007.
Level

Easy3 of 10

Topics
Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

An ascending number is a number whose digits never decrease from left to right. Two adjacent digits that are equal still count as ascending.

For example, 2234, 3678, and 11119 are ascending numbers, while 2232, 3676, and 91111 are not.

Given the length NN, write a program that counts the ascending numbers of length NN. The leading digit may be 0.

Input

The first line contains NN. (1≤N≤10001 \le N \le 1000)

Output

Print the number of ascending numbers of length NN, modulo 1000710007, on the first line.

Examples3

  1. Example 1

    Input
    1
    Expected output
    10

  2. Example 2

    Input
    2
    Expected output
    55

  3. Example 3

    Input
    3
    Expected output
    220