神奇的护腕

神奇的护腕

测试数据来自 system/1970

描述

过年往往是走亲访友的时节,不过今天我得去拜访一位特殊的朋友。
听说,前几天的某一深夜,万籁俱寂,棂又经历了一场恶战,不但身体被剧烈消耗,又伤得不轻,看来他是过不了一个好年了。
今天,我,SE集团252地区的负责人之一,来到了与棂的联络站,传达组织上的指示。组织上建议几乎完全失去法力的棂调到空间科研所工作,对他来说继续战斗太危险了。
棂说:“实际上我还能坚持下去,¥#@%&……那天拉尔法正召集手下开会,根本没想到会被我和晓筱撞上,他甚至没想到我还活着。他以为我早就被那些小毛贼‘分而食之’了。
“不过我还有这个。”棂轻抬手腕,随即一片碧蓝色的光柔柔地向我洒来。
那是一只精致的碧蓝色护腕,几乎通体透明。护腕表面镶嵌着翠绿的多向石,石上零星地点缀着些正发出微光的微粒。透过表面向里看去,里面是一棵二叉树。护腕内部的空间仿佛延伸到了四维,整棵树虽只有n个结点,但看上去在任何方向上都无限延伸。树上不时有一些点进行Splay操作。
棂:“虽然整棵树可以进行Splay,但结点之间没有大小关系。”
我:“那不就退化成一棵普通二叉树了吗?”
棂:“虽然如此,但这样的树是灵活多变的,我的对手很难知道这棵树的总形态数,所以多少会怀疑这棵树多变的形态中究竟隐藏着什么秘密。对手猜不透我,我的机会就会增加。不如你来试试,现在这棵树一共有多少种可能的形态?”

格式

输入格式

输入有多组数据,每一行为一个整数n。

输出格式

对每一行输入,输出一行一个整数,为总的形态数对500009取模后的值。

样例1

样例输入1

1
2
3

样例输出1

1
2
5

限制

对于30%的数据,n≤5×10^3;
对于60%的数据,n≤5×10^5;
对于100%的数据,n≤10^10,每个测试点数据组数不超过10^4组。

提示

  • 500009是棂十分喜欢的质数。
  • 运行cmd,输入start mspaint... 然后请自行脑补样例输入输出。 【后记】
  • 10s后,棂说:“怎么样,算不出来了吧?真正到了战斗中,送给对手10秒钟对自己来说是绝对致命的。不过这个东西的用处远不止这些\(@^%\)##^blabla……” “停停停啊,我知道了啊,那调动的事过一段时间再和组织上商量吧,好好养伤啊,这段时间你的职务由晓筱代理啊,你不用操心了啊,我走了啊,再见啊!” 棂:“哎,记得帮我查一查拉尔法是什么情况啊!”

信息

ID
2001
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者