请问什么情况下会答案会等于 $10^9+1$ ？

赛时一直没明白WA了好多次才AC。赛后assert了一下确实有答案是 $10^9+1$ 的情况。