战士与卡牌
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
小明在玩一款肉鸽卡牌游戏，他扮演一名战士，通过打出手牌来战胜敌人。现在他的初始牌堆中只有两张不同的牌，分别称为“斩击”和“倍增”。
两张牌的规则如下：
-
斩击：
打出“斩击”时，统计当前牌堆中除“斩击”自身以外的所有卡牌数量。
每有 1 张其他卡牌，“斩击”就造成 1 点伤害。
“斩击”的基础伤害为 0。
打出后，“斩击”会回到牌堆。 -
倍增：
打出“倍增”后，牌堆中“倍增”这种牌的数量翻倍。
打出后，“倍增”会回到牌堆。
初始时，牌堆中有：
- “斩击” 1 张；
- “倍增” 1 张；
- 没有其他牌。
小明先连续打出“倍增”牌共 (n) 次。在这 (n) 次中，他不打出“斩击”。
在这 (n) 次之后，小明第一次打出“斩击”。
请你计算：这次打出的“斩击”能造成多少点伤害？
输入格式
输入一个整数n
输出格式
输出最后伤害对1e5+3取模得到的数。
测试用例
114
85261
数据规模与约定
1s, 1024KiB for each test case.