输入描述:

在一行上输入一个整数 ，表示待查询的数字。

输出描述:

新起一行输出一个整数，表示答案对  取模后的结果。

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-30 优化题面文本与格式。模板题为便于测试，将时间限制扩充至 5s，空间限制扩充至 1024MB。