package main import . "fmt" import . "math/big" type Modulo struct { k *Int } // Goの剰余演算子 % は負を割る場合… // big.IntにはDiv/ModとQuo/Remの2つあり、演算子 % は後者Rem… // WHY!? func (m Modulo) Modi(a int) int { return int(new(Int).Mod(NewInt(int64(a)), m.k).Int64()) } type Mat struct { a,b int c,d int } type Vec struct { s int t int } func (m1 *Mat) MulMat(m2 *Mat, k Modulo) *Mat { return &Mat{ a: k.Modi(k.Modi(m1.a*m2.a) + k.Modi(m1.b*m2.c)), b: k.Modi(k.Modi(m1.a*m2.b) + k.Modi(m1.b*m2.d)), c: k.Modi(k.Modi(m1.c*m2.a) + k.Modi(m1.d*m2.c)), d: k.Modi(k.Modi(m1.c*m2.b) + k.Modi(m1.d*m2.d)), } } func (m *Mat) MulVec(v *Vec, k Modulo) *Vec { return &Vec{ s: k.Modi(k.Modi(m.a*v.s)+k.Modi(m.b*v.t)), t: k.Modi(k.Modi(m.c*v.s)+k.Modi(m.d*v.t)), } } func (m *Mat) Pow(n int, k Modulo) *Mat{ if n == 0 { return &Mat{ 1, 0, 0, 1, } } else if n == 1 { return m } else if n % 2 == 0 { dm := m.MulMat(m, k) return dm.Pow(n/2, k) } else { dm := m.MulMat(m, k) return dm.Pow(n/2, k).MulMat(m, k) } } func main() { var m Mat var v Vec var n int var k Int Scan(&m.a,&m.b,&m.c,&m.d,&v.s,&v.t,&n,&k) ans := m.Pow(n, Modulo{&k}).MulVec(&v, Modulo{&k}) Println(ans.s, ans.t) }