题目描述

小明在玩一款肉鸽卡牌游戏，他扮演一名战士，通过打出手牌来战胜敌人。现在他的初始牌堆中只有两张不同的牌，分别称为“斩击”和“倍增”。

两张牌的规则如下：

1. 斩击：
   打出“斩击”时，统计当前牌堆中除“斩击”自身以外的所有卡牌数量。
   每有 1 张其他卡牌，“斩击”就造成 1 点伤害。
   “斩击”的基础伤害为 0。
   打出后，“斩击”会回到牌堆。

2. 倍增：
   打出“倍增”后，牌堆中“倍增”这种牌的数量翻倍。
   打出后，“倍增”会回到牌堆。

初始时，牌堆中有：

• “斩击” 1 张；
• “倍增” 1 张；
• 没有其他牌。

小明先连续打出“倍增”牌共 (n) 次。在这 (n) 次中，他不打出“斩击”。
在这 (n) 次之后，小明第一次打出“斩击”。

请你计算：这次打出的“斩击”能造成多少点伤害？

输入格式

输入一个整数n

输出格式

输出最后伤害对1e5+3取模得到的数。

测试用例

114

85261

数据规模与约定

$0 \le n \le 2^{63}$

1s, 1024KiB for each test case.