Problem2770--牛式 Prime Cryptarithm [USACO1.4]

2770: 牛式 Prime Cryptarithm [USACO1.4]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

在美国的学校里,多位数乘法以及“部分乘积”的解释,如下:

上图是一个三位数adc乘以两位数de的乘法竖式,
e乘以abc在“部分乘积”中叫第一部分即上图中的p1,也就是第二个数的个位和第一个数的积
d乘以abc在“部分乘积”中叫第二部分即上图中的p2,也就是第二个数的十位和第一个数的乘积
p1和p2的和就是最终的答案,也就是:e*abc + 10*d*abc) == de*abc


下面是一个乘法的竖式,如果用我们给定的N个数字来取代*,可以使式子成立的话,我们就叫这个式子牛式。

数字只能取代*,当然第一位不能为0,况且给定的数字里不包括0。
写一个程序找出所有满足上述条件的牛式。其中abc是三位数,de是两位数,p1、p2是三位数,abc*de是四位数。

Input

第一行:一个整数N,表示将要被使用到的数字的个数
第二行:N个用空格隔开的数字(每个数字都属于{1,2,3,4,5,6,7,8,9})。

Output

共一行,一个数字。表示牛式的总数。

Sample Input Copy

5
2 3 4 6 8

Sample Output Copy

1

HINT

输入样例的唯一解决方案

Source/Category