SP18184 DURIN - Durins Day

在《霍比特人：史矛革之战》中，J. R. R. 托尔金决定给索林·橡木盾增加困难。这次，他得到了一组由一个小字符串表示的无限多的钥匙。而隐藏入口前有许多并排的锁孔，表示为一个长字符串。只有当钥匙和锁孔完全匹配时，钥匙才能插入。 橡木盾不清楚他需要多少把钥匙，也不知道具体需要尝试哪些锁孔。如果有 **n** 个锁孔可以插入钥匙，那么他可能需要使用从 **1 到 n** 把钥匙（包括两端）。此外，他需要从所有可以插入的锁孔中选择出需要使用的那几个。索林只知道有一种唯一的方法可以打开门。 尝试每种可能的钥匙配置需要花费 **1** 秒的时间。而杜林日的最后一缕阳光不会持续很久，他必须在光线消失前测试完所有的可能性。你的任务是计算出，在最坏的情况下，他可能需要多少时间。 由于答案可能非常大，请将结果对 **1000000007** 取模后输出。如果没有任何锁孔可以插入钥匙，请输出 0。 **本翻译由 AI 自动生成**

无

无