Roads
Roads
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).
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 (1 ≤ n ≤ 20).
Output data
Print the number of different roads of length n.
Examples
1
10