Problem E. Express Lines

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define ppb pop_back()
#define mkp make_pair
#define sz(a) (ll)a.size()

const ll MAXN=1e6+5;
const ll INF=1e18;
const ll MOD=998244353;

ll N,K,dp[2][MAXN][2]; // 編號、當前顏色 0:黑色

void solve(){
    while(cin>>N>>K){
        dp[0][0][0]=dp[1][0][1]=1;
        for(ll i=0;i<2;i++){ // 是否 1 st stop 有停
            for(ll j=1;j<N;j++){
                dp[i][j][0]=dp[i][j-1][1]%K;
                dp[i][j][1]=(dp[i][j-1][1]+dp[i][j-1][0])%K;
            }
        }
        cout<<((dp[0][N-1][1]+dp[1][N-1][0]+dp[1][N-1][1]-1-N)%K+K)%K<<'\n';
        // 都不選、只選一站
    }
}

signed main(){
    fastio
    freopen("express.in","r",stdin);
    freopen("express.out","w",stdout);
    // ll T;
    // cin>>T;
    solve();
    return 0;
}