记录编号	39315	评测结果	AAAAAAAAAA
题目名称	项链制作	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	1.257 s
提交时间	2012-07-08 21:05:33	内存使用	1.19 MiB

const op:array[1..16] of longint=
(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,
32768);
 mt:int64=1000000007;
var
 f,g:array[0..66666] of int64;
 c:array[1..16,1..16] of int64;
 i,j,m,n,k:longint;
 procedure dfs(s:longint);
 var i,j,bj,y:longint;ot:int64;
 begin
  if g[s]>-1 then exit;
  ot:=0;
  for i:=1 to n do
   if (op[i] and s=op[i]) then break;
  y:=i;
  i:=s and (s-1);
  while true do begin
    if (op[y] and i=op[y]) then
    begin
    dfs(i);
    bj:=i xor s;
    ot:=(ot+(f[bj]*g[i]) mod mt) mod mt;
    end;
    if i=0 then break;
    i:=(i-1) and s;
   end;
  g[s]:=(f[s]-ot+mt) mod mt;
 end;
begin
 assign(input,'necklacemn.in');reset(input);
 assign(output,'necklacemn.out');rewrite(output);
 readln(n);
 for i:=1 to n do
  begin
    for j:=1 to n do read(c[i,j]);
    readln;
  end;
  m:=(1 shl n)-1;
  fillchar(g,sizeof(g),$ff);
  for k:=0 to m do
   begin
    f[k]:=1;
    for i:=1 to n do
     if  (op[i] and k=op[i]) then
     for j:=i+1 to n do
      if (op[j] and k=op[j]) then
      f[k]:=(f[k]*(c[i,j]+1)) mod mt;
   end;
  g[0]:=1;
  dfs(m);
  writeln(g[m]);
  close(input);close(output);
end.