魔法师小A有n颗糖果，现在他把这些糖果排成一列，用1~n表示。现在他想把这些糖果合并成一颗大糖果。每次合成操作，他有两种合成魔法：

1.添加α魔药，将最后一颗糖果合并到前一颗糖果中；

2.如果糖果数量为偶数，添加β魔药，将后一半所有糖果合并到前一颗糖果中。

由于这两种合成魔法原理不同，小A想知道他有多少种本质不同的合成方法让这n颗糖果合成为一颗糖果。

仅一个正整数n，代表糖果数量。

仅一个正整数，代表合成方法的方案数。

在这个样例中，小A有2颗糖果，仅需一次操作即可变为1颗糖果，他可以用第一种魔法合成，也可以用第二种魔法合成。

【数据范围】
对于30%的数据，n≤3000。 
对于60%的数据，n≤100000。
对于100%的数据，2≤n≤500000。

2025瑞安小学组复赛