入力が高々 \(9\) 通りなので, 答えをあらかじめ用意しておくのが手っ取り早い.