eolymp
bolt
Try our new interface for solving problems

Roads

Time limit 1 second
Memory limit 122 MiB

Since ancient times Russia (as it turns out, not only this country) is known for its bad roads. However, starting from the day after tomorrow, this problem will be solved! Ministry of Railways Mendeleevo (and not only it) has developed a new reform designed to significantly improve the quality of roads. The reform is as follows:

  • Each road being constructed contains n segments of width 1 meter.

  • Each road segment has integer height from 0 till 9 meters above the sea level.

  • The difference in height between two consecutive segments must not be more than 1 meter (that is, each successive segment has to be higher than the previous one on**-1**, 0 or 1 meter).

prb5106

Millions of domestic motorists are already rejoicing, admiring the new reform. The only issue that they care about is how many different ways of length n can be built in such way? Roads considered equal if each segment of the first road coincides in height with the corresponding segment of a second road.

Input data

One number n (1n20).

Output data

Print the number of different roads of length n.

Examples

Input example #1
1
Output example #1
10