(关键词-Input)

Description

在一串未打结的项链上(意思就是说项链的左端和右端不相连)，有N颗珠子，你有M种颜色，然后就问你有多少种方法将每一颗珠子都染上颜色，使得任意两颗相邻的珠子的颜色不同。
Input

输入只有一行，三个正整数N、M和P，之间以一个空格隔开。
Output

输出只有一行，表示染色的方法总数模P。
Sample Input
5 4 13
Sample Output
12
HINT

样例一共有324种染色方法，对13取模后是12。

对于10%的数据，N=1，M<=10，P<=10；

对于20%的数据，N<=10，M<=10，P<=100；

对于50%的数据，N,M,P<=1,000,000,000；

对于100%的数据，1<=N,M,P<=1,000,000,000,000,000,000，且M>=2。

TLE代码贴一个，可以用stl，但是不能用vector

#include <iostream>
using namespace std;
long long dp[2]; 
long long ans(long long N, long long M, long long P) {
    dp[1] = M;
    for (int i = 2; i <= N; ++i) {
        dp[i % 2] = (dp[(i - 1) % 2] * (M - 1)) % P;
    }
    return dp[N % 2];
}

int main() {
    long long N, M, P;
    cin >> N >> M >> P;
    long long result = ans(N, M, P);
    cout << result;
    return 0;
}