#include <iostream>
using namespace std;
const int c = 2009;
int main( ) {
int n, p, s, i, j, t;
cin >> n >> p;
s = 0;
t = 1;
for (i = 1; i <= n; i++) {
t = t * p % c;
for (j = 1; j <= i; j++)
s = (s + t) % c;
}
cout << s << endl;
return 0;
}
输入：11 2
输出：1
