ADBRACK – SPOJ

const   fi='';
        fo='';
        maxn=100+3;
var     f       :array[-maxn..maxn,-maxn..maxn] of ansistring;
        i,j,n,k :longint;
        st      :ansistring;
        p       :longint;
        res     :ansistring;
        stack   :array[1..maxn] of char;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n,k);
        readln(st);
        close(input);
end;
procedure init;
begin
        for i:=0 to n+1 do
                for j:=0 to n+1 do f[i,j]:='-1';
end;
function cong (a,b: ansistring): ansistring;
var     nho,tam,i:longint;
        res     :ansistring;
begin
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        nho:=0; res:='';
        for i:=length(a) downto 1 do
                begin
                        tam:=ord(a[i])+ord(b[i])-96+nho;
                        nho:=tam div 10;
                        tam:=tam mod 10;
                        res:=chr(tam+48)+res;
                end;
        if nho>0 then res:='1'+res;
        exit(res);
end;
function tinh(i,c:longint):ansistring;
var     sl      :ansistring;
begin
        if f[i,c]<>'-1' then exit(f[i,c]);
        if i>n then
                if c=0 then
                        begin
                                f[i,c]:='1';
                                exit('1')
                        end
                        else
                        begin
                                f[i,c]:='0';
                                exit('0');
                        end;
        sl:= '0';
                if c<k then
                begin
                stack[c+1]:='(';
                sl := cong( sl, tinh(i+1,c+1) );
                stack[c+1]:='[';
                sl := cong( sl, tinh(i+1,c+1) );
                stack[c+1]:='{';
                sl := cong( sl, tinh(i+1,c+1) );
                end;
                if c>0 then
                sl := cong( sl, tinh(i+1,c-1) );
        f[i,c]:=sl;
        exit(sl);
end;
procedure timkq(i,c:longint);
begin
        if i>n then
                begin
                        res:=cong(res,'1');
                        writeln(res);
                        halt;
                end;
        if st[i]='(' then
                begin
                        stack[c+1]:='(';
                        timkq(i+1,c+1);
                end
        else
                if c<k then
                begin
                        stack[c+1]:='(';
                        res:=cong(res, tinh(i+1,c+1));
                end;
        if st[i]=')' then
                begin
                        timkq(i+1,c-1);
                end
        else
                begin
                        if c>0 then
                        if stack[c]='(' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='[' then
                begin
                        stack[c+1]:='[';
                        timkq(i+1,c+1) ;
                end
        else
                if c<k then
                begin
                        stack[c+1]:='[';
                        res:=cong(res, tinh(i+1,c+1));
                end;
        if st[i]=']' then
                begin
                        timkq(i+1,c-1) ;
                end
        else
                begin
                        if c>0 then
                        if stack[c]='[' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='{' then
                begin
                        stack[c+1]:='{';
                        timkq(i+1,c+1);
                end
        else
                if c<k then
                begin
                        stack[c+1]:='{';
                        res:=cong(res,tinh(i+1,c+1));
                end;
        if st[i]='}' then
                begin
                        timkq(i+1,c-1);
                end
        else
                begin
                        if c>0 then
                        if stack[c]='{' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
end;
procedure process;
var     tam:ansistring;
begin
assign(output,fo);rewrite(output);
        tam := tinh(1,0);
        res:='0';
        stack:='';
        timkq(1,0);
close(output);
end;
begin
        enter;
        init;
        process;
end.

const fi=''; fo=''; maxn=100+3; var f :array[-maxn..maxn,-maxn..maxn] of ansistring; i,j,n,k :longint; st :ansistring; p :longint; res :ansistring; stack :array[1..maxn] of char; procedure enter; begin assign(input,fi);reset(input); readln(n,k); readln(st); close(input); end; procedure init; begin for i:=0 to n+1 do for j:=0 to n+1 do f[i,j]:='-1'; end; function cong (a,b: ansistring): ansistring; var nho,tam,i:longint; res :ansistring; begin while length(a)<length(b) do a:='0'+a; while length(b)<length(a) do b:='0'+b; nho:=0; res:=''; for i:=length(a) downto 1 do begin tam:=ord(a[i])+ord(b[i])-96+nho; nho:=tam div 10; tam:=tam mod 10; res:=chr(tam+48)+res; end; if nho>0 then res:='1'+res; exit(res); end; function tinh(i,c:longint):ansistring; var sl :ansistring; begin if f[i,c]<>'-1' then exit(f[i,c]); if i>n then if c=0 then begin f[i,c]:='1'; exit('1') end else begin f[i,c]:='0'; exit('0'); end; sl:= '0'; if c<k then begin stack[c+1]:='('; sl := cong( sl, tinh(i+1,c+1) ); stack[c+1]:='['; sl := cong( sl, tinh(i+1,c+1) ); stack[c+1]:='{'; sl := cong( sl, tinh(i+1,c+1) ); end; if c>0 then sl := cong( sl, tinh(i+1,c-1) ); f[i,c]:=sl; exit(sl); end; procedure timkq(i,c:longint); begin if i>n then begin res:=cong(res,'1'); writeln(res); halt; end; if st[i]='(' then begin stack[c+1]:='('; timkq(i+1,c+1); end else if c<k then begin stack[c+1]:='('; res:=cong(res, tinh(i+1,c+1)); end; if st[i]=')' then begin timkq(i+1,c-1); end else begin if c>0 then if stack[c]='(' then res:=cong(res,tinh(i+1,c-1)); end; if st[i]='[' then begin stack[c+1]:='['; timkq(i+1,c+1) ; end else if c<k then begin stack[c+1]:='['; res:=cong(res, tinh(i+1,c+1)); end; if st[i]=']' then begin timkq(i+1,c-1) ; end else begin if c>0 then if stack[c]='[' then res:=cong(res,tinh(i+1,c-1)); end; if st[i]='{' then begin stack[c+1]:='{'; timkq(i+1,c+1); end else if c<k then begin stack[c+1]:='{'; res:=cong(res,tinh(i+1,c+1)); end; if st[i]='}' then begin timkq(i+1,c-1); end else begin if c>0 then if stack[c]='{' then res:=cong(res,tinh(i+1,c-1)); end; end; procedure process; var tam:ansistring; begin assign(output,fo);rewrite(output); tam := tinh(1,0); res:='0'; stack:=''; timkq(1,0); close(output); end; begin enter; init; process; end.