import scala.collection.mutable
import scala.io.StdIn

object Main extends App{
  def memo[argT2,retT](f:(Int,argT2)=>retT):(Int,argT2)=>retT = {
    val m = mutable.ArrayBuffer.empty[retT]
    (arg1,arg2) => {
      (m.size to arg1).foreach(i=>m+=f(i,arg2))
      if(arg1<0) f(arg1,arg2) else m(arg1)
    }
  }
  var inv: (Int,Int)=>Long = memo{
    case (m: Int, mod: Int) if m > 1 => ((mod - mod / m) * inv(mod % m, mod)) % mod
    case _ => 1
  }
  var fact: (Int,Int)=>Long = memo {
    case (m: Int, mod: Int) if m > 0 => (m * fact(m - 1, mod)) % mod
    case _ => 1
  }
  var factr: (Int,Int)=>Long = memo {
    case (m: Int, mod: Int) if m > 0 => (inv(m, mod) * factr(m - 1, mod)) % mod
    case (0, _) => 1
    case _ => 0
  }
  def combination_len(n:Int,r:Int,mod:Int): Int           = (fact(n,mod)*factr(r,mod)%mod*factr(n-r,mod)%mod).toInt
  def repeated_combination_len(n:Int,r:Int,mod:Int): Int  = combination_len(n+r-1,r,mod)
  def permutation_len(n:Int,r:Int,mod:Int): Int           = (fact(n,mod)*factr(n-r,mod)%mod).toInt
  val mod = 1000000007
  val n = StdIn.readInt()
  val ans = Array.fill(n){
    val a = StdIn.readLine().split("\\(|\\)|,")
    a(0) match {
      case "C" => combination_len(a(1).toInt,a(2).toInt,mod)
      case "P" => permutation_len(a(1).toInt,a(2).toInt,mod)
      case "H" => repeated_combination_len(a(1).toInt,a(2).toInt,mod)
    }
  }
  println(ans.mkString("\n"))
}