#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; template struct Matrix{ vector> a; Matrix(){} Matrix(size_t n, size_t m):a(n, vector(m, 0)){} Matrix(size_t n):Matrix(n, n){} Matrix(vector> a):a(a){} size_t height() const{ return a.size(); } size_t width() const{ return a[0].size(); } inline const vector &operator[](size_t k) const{ return a[k]; } inline vector &operator[](size_t k){ return a[k]; } static Matrix I(size_t n){ Matrix mat(n); for(int i=0; i> c(n, vector(l, 0)); for(int i=0; i>=1; } return ret; } static pair Gauss_Jordan(const Matrix &a, const Matrix &b){ size_t n=a.height(), m=a.width(), l=b.width(); Matrix c(n, m+l); for(int i=0; i, vector>> linear_equations(const Matrix &a, const vector &b){ int n=a.height(), m=a.width(); Matrix B(n, 1); for(int i=0; i myon(n,-1); vector nuo(m, -1); for(int i=0; i retc; vector> retd; return make_pair(retc, retd); } } vector c(m); vector> d; for(int i=0; i v(m); v[i]=1; for(int j=0; j; int main() { ll c, n, m; cin>>c>>n>>m; Mat mat(4); mint x0=mint(c).inv(), x1=mint(c-1).inv(); mat[0][0]=x0, mat[0][2]=x0*(c-1), mat[1][1]=x0, mat[1][3]=x0*(c-1), mat[2][1]=x1, mat[3][0]=x1, mat[3][1]=x1*(c-2); mat=mat.pow(n); mint p=mat[0][1]*(c-1)+mat[0][2]+mat[0][3]*(c-1); mint ans=1-(p.pow(m)); cout<