0848 - 虫食い算

時間制限 2 秒 / メモリ制限 256 MB / 得点 6 / Writer root / x 1 / 統計 /


TLE
2sec
MLE
256MB
得点
6

足し算は筆算で簡単に計算できますが、もし、いくつかの数字が欠けていたら、欠けている数字を埋めるのは簡単でしょうか? 例えば、以下のような筆算において、1から9の数字が一度しか現れないという条件があるとき、CとEのマスに入る数字はいくつになるでしょう? この場合、Cに入るのは8,Eに入るのは5が正解となります。このように、数字がいくつか欠けている演算を虫食い算と呼びます。



1から9の数字が一度しか現れないという条件はそのままで、以下のようにもっとたくさんの数字が欠けていたら、正解となる数字の埋め方は一通りしかないのでしょうか? 実は、必ず一通りに決まるとは限りません。



上の図のような形をした虫食い算の、AからIの各マスの情報が与えられたとき、正しい埋め方が何通りあるかを出力するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

A B C D E F G H I

1行に、虫食い算の から のマスに入っている数字の情報が与えられる。ただし、与えられた値が -1 のときは、そのマスの数字が欠けていることを表す。-1 以外の値は、1 から 9 の整数のいずれかで、それらの間に重複はない。

出力

正しい埋め方が何通りあるかを1行に出力する。

入力例 1

7 6 -1 1 -1 9 2 3 4

出力例 1

1

入力例 2

7 6 5 1 8 9 2 3 4

出力例 2

0

入力例 3

-1 -1 -1 -1 -1 -1 8 4 6

出力例 3

12

入力例 4

-1 -1 -1 -1 -1 -1 -1 -1 -1

出力例 4

168