Majid has cubic bricks with a unit side length. He wants to arrange these bricks as adjacent columns, such that the height of each column is not less than the height of the previous column. For example, if Majid has two bricks, he can arrange them in two ways. In the first arrangement, he can form a column with a height of , and in the second arrangement, he can create two columns with heights of each. Majid wants to know in how many ways he can do this. Given , calculate the number of possible desired arrangements.
The input consists of a single integer , which represents the number of bricks Majid has.
Print a single line containing the number of desired arrangements of the bricks. Since this number can be very large, print its remainder modulo .