package main import ( "bufio" "fmt" "io" "os" "strconv" ) var iost *Iost type Iost struct { Scanner *bufio.Scanner Writer *bufio.Writer } func NewIost(fp io.Reader, wfp io.Writer) *Iost { const BufSize = 2000005 scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, BufSize), BufSize) return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)} } func (i *Iost) Text() string { if !i.Scanner.Scan() { panic("scan failed") } return i.Scanner.Text() } func (i *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x } func (i *Iost) GetNextInt() int { return i.Atoi(i.Text()) } func (i *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x } func (i *Iost) GetNextInt64() int64 { return i.Atoi64(i.Text()) } func (i *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x } func (i *Iost) GetNextFloat64() float64 { return i.Atof64(i.Text()) } func (i *Iost) Print(x ...interface{}) { fmt.Fprint(i.Writer, x...) } func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) } func (i *Iost) Println(x ...interface{}) { fmt.Fprintln(i.Writer, x...) } func isLocal() bool { return os.Getenv("I") == "IronMan" } func main() { fp := os.Stdin wfp := os.Stdout if isLocal() { fp, _ = os.Open(os.Getenv("END_GAME")) } iost = NewIost(fp, wfp) defer func() { if isLocal() { iost.Println(recover()) } iost.Writer.Flush() }() solve() for i := 0; isLocal() && i < 100; i++ { iost.Println("-----------------------------------") solve() } } func solve() { SetMod(Mod1000000007) n := iost.GetNextInt() m := iost.GetNextInt() tt := make([]int, m) xx := make([]int, m) yy := make([]int, m) mc := newModcom(n * 2) ans := calc(n, n, mc) for i := 0; i < m; i++ { tt[i] = iost.GetNextInt() xx[i] = iost.GetNextInt() yy[i] = iost.GetNextInt() if tt[i] == 1 { ans.SubAs(mc.Choose(xx[i]+yy[i], yy[i]).Mul(mc.Choose(n-(xx[i]+1)+n-yy[i], n-yy[i]))) continue } ans.SubAs(mc.Choose(xx[i]+yy[i], yy[i]).Mul(mc.Choose(n-xx[i]+n-(yy[i]+1), n-xx[i]))) } iost.Println(ans) } func calc(r, c int, mc modcom) Mint { return mc.Choose(r+c, r).Mul(Mint(r + c)) } // Mod constants. const ( Mod1000000007 = 1000000007 Mod998244353 = 998244353 ) var ( mod Mint fmod func(Mint) Mint ) // Mint treats the modular arithmetic type Mint int64 // SetMod sets the mod. It must be called first. func SetMod(newmod Mint) { switch newmod { case Mod1000000007: fmod = staticMod1000000007 case Mod998244353: fmod = staticMod998244353 default: mod = newmod fmod = dynamicMod } } func dynamicMod(m Mint) Mint { m %= mod if m < 0 { return m + mod } return m } func staticMod1000000007(m Mint) Mint { m %= Mod1000000007 if m < 0 { return m + Mod1000000007 } return m } func staticMod998244353(m Mint) Mint { m %= Mod998244353 if m < 0 { return m + Mod998244353 } return m } // Mod returns m % mod. func (m Mint) Mod() Mint { return fmod(m) } // Inv returns modular multiplicative inverse func (m Mint) Inv() Mint { return m.Pow(Mint(0).Sub(2)) } // Pow returns m^n func (m Mint) Pow(n Mint) Mint { p := Mint(1) for n > 0 { if n&1 == 1 { p.MulAs(m) } m.MulAs(m) n >>= 1 } return p } // Add returns m+x func (m Mint) Add(x Mint) Mint { return (m + x).Mod() } // Sub returns m-x func (m Mint) Sub(x Mint) Mint { return (m - x).Mod() } // Mul returns m*x func (m Mint) Mul(x Mint) Mint { return (m * x).Mod() } // Div returns m/x func (m Mint) Div(x Mint) Mint { return m.Mul(x.Inv()) } // AddAs assigns *m + x to *m and returns m func (m *Mint) AddAs(x Mint) *Mint { *m = m.Add(x) return m } // SubAs assigns *m - x to *m and returns m func (m *Mint) SubAs(x Mint) *Mint { *m = m.Sub(x) return m } // MulAs assigns *m * x to *m and returns m func (m *Mint) MulAs(x Mint) *Mint { *m = m.Mul(x) return m } // DivAs assigns *m / x to *m and returns m func (m *Mint) DivAs(x Mint) *Mint { *m = m.Div(x) return m } type modcom struct { Facs, Invs []Mint } func newModcom(n int) modcom { facs := make([]Mint, n+1) invs := make([]Mint, n+1) facs[0] = 1 for i := 0; i < n; i++ { facs[i+1] = facs[i].Mul(Mint(i + 1)) } invs[n] = facs[n].Inv() for i := n - 1; i >= 0; i-- { invs[i] = invs[i+1].Mul(Mint(i + 1)) } return modcom{ Facs: facs, Invs: invs, } } func (mc *modcom) Choose(n, k int) Mint { if n < len(mc.Facs) { return mc.Facs[n].Mul(mc.Invs[k]).Mul(mc.Invs[n-k]) } ans := mc.Invs[k] for k > 0 { ans.MulAs(Mint(n).Mod()) n-- k-- } return ans }