N problems have been chosen by the judges, now it's time to assign scores to them!

Problem i must get an integer score A_i between 1 and N, inclusive. The problems have already been sorted by difficulty: A_1 \le A_2 \le \ldots \le A_N must hold. Different problems can have the same score, though.

Being an ICPC fan, you want contestants who solve more problems to be ranked higher. That's why, for any k (1 \le k \le N-1), you want the sum of scores of any k problems to be strictly less than the sum of scores of any k+1 problems.

How many ways to assign scores do you have? Find this number modulo the given prime M.

Constraints

* 2 \leq N \leq 5000
* 9 \times 10^8 < M < 10^9
* M is a prime.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N M


Output

Print the number of ways to assign scores to the problems, modulo M.

Examples

Input

2 998244353


Output

3


Input

3 998244353


Output

7


Input

6 966666661


Output

66


Input

96 925309799


Output

83779
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vp;
const int inf = 1e9;
const ll INF = 1e18;
const db eps = 1e-10;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ep emplace
#define mem(a) memset(a, 0, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(b))
#define PA cout << "pass\n"
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define TM cout << db(clock()) / CLOCKS_PER_SEC << '\n'

const int maxn = 5050;
int f[maxn];

int n, mod;
void add(int &x, int y){
    x += y;
    if(x >= mod) x -= mod;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> mod;
    f[0] = 1;
    for(int i = 2; i <= n; i++){
        int t = min(i - 1, n + 2 - i);
        for(int j = t; j <= n; j++){
            add(f[j], f[j -  t]);
        }
    }
    int res = 0;
    for(int i = 0; i <= n; i++) add(res, 1ll * f[i] * (n - i) % mod);
    cout << res << '\n';
    return 0;
}