SP7897 SKYLINE - Skyline

新电影的导演需要为电影创建一个缩放布景。在这个集合中将有N座摩天大楼，高度从1米到N米不等。天际线将由摩天大楼从左到右的高度顺序决定。它是整数从1到N的排列。 导演非常细致，所以她想避免某种倾斜的模式。她不希望在位置i, j, k中有任意三栋建筑，i < j < k，其中建筑i的高度小于建筑j的高度，并且建筑j的高度小于建筑k的高度。 你的任务是告诉主管，对于给定数量的建筑物，有多少不同的天际线顺序可以避免她不喜欢的倾斜模式。

在输入中将有几个测试用例。每个测试用例将由包含单个整数N的单行组成

对于每个测试用例，输出一个整数，表示良好天际线的数量——避免了导演不喜欢的倾斜模式——对1,000,000取模。在单独的行上打印每个整数，不带空格。答案之间不要有空白行。