三、完善程序（单选题，每小题3分，共计30分）

第1题

给定整数 $N$、$A$ 以及 $M$，请计算并输出：

using i64 = long long;
std::pair<i64, i64> solve(i64 n, i64 A, i64 M)
{
    if (n == 0)
        return {____(1)____};
    else if (n % 2 == 1) {
        auto result = solve(____(2)____, A, M);
        auto sum = result.first;
        auto pow = result.second;
        sum = ____(3)____;
        pow = pow * A % M;
        return {sum, pow};
    }
    else {
        auto result = solve(____(4)____, A, M);
        auto sum = result.first;
        auto pow = result.second;
        sum = ____(5)____;
        pow = ____(6)____;
        return {sum, pow};
    }
}

int main()
{
    i64 N, A, M;
    std::cin >> N >> A >> M;
    std::cout << solve(N, A, M).first << "\n";
}

（2）（4）处应填（ ）。

{{ select(1) }}

• n - 1, n - 1
• n - 1, n / 2
• n / 2, n - 1
• n / 2, n / 2