Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ072 - PTwPZ Planeta Bin-Bin

Planeta Bin-Bin

Treść

W odległej galaktyce Duo-Duo, na planecie Bin-Bin żyje sobie rasa Bin-Binitów. Budowa ciała Bin-Binitów bardzo przypomina ludzką. Odróżnia nas od siebie kolor skóry (Bin-Binici są zieleni) oraz liczba palców na każdej z kończyn. Mieszkańcy planety Bin-Bin posiadają po dwa palce na każdej z rąk i nóg. Mniejsza liczba palców niesie za sobą wiele korzyści. Obcinanie paznokci trwa zdecydowanie krócej, produkcja rękawiczek jest znacznie prostsza, a wydatki na pierścionki są o wiele niższe niż na Ziemi. Oprócz tego Bin-Binici posługują się prostszym, dwójkowym systemem liczbowym.

Do obliczania wartości wyrażeń typu (a + b)n stosuje się tu tzw. wzór Bintona na dwumian:

 
k = n
(a + b)n  =    cn, k · an - k · bk ,   gdzie
 
k = 0
cn, k  = 
n!
k! · (n - k)!

Obliczanie współczynników cn,k, podobnie jak na Ziemi nie jest zadaniem trywialnym, zwłaszcza gdy n jest dużą, 20- lub 30-cyfrową liczbą. Bin-Biniccy informatycy postanowili rozwiązać ten problem przez napisanie oprogramowania, które będzie obliczać współczynniki cn,k. Aby uprościć zadanie zdecydowali się obliczać każdą cyfrę wyniku oddzielnie, a następnie składać otrzymane wyniki w końcowy rezultat. Tobie, jako zaprzyjaźnionemu programiście z Ziemi, przypadła w udziale procedura obliczająca najmniej znaczącą cyfrę wyniku. Napisz program, który będzie taką procedurę zawierał.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Jeden zestaw danych obejmuje dwa wiersze. W pierwszym podana jest liczba n, a w drugim k (0<=k<=n). Obie liczby podane są w postaci dwójkowej, a ich długość nie przekracza 30 cyfr.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest najmniej znacząca cyfra współczynnika cn,k dwumianu Bintona.

Przykład

dane wejściowe:
2
101
1
100000000000000000000000000000
1001010010000110101111

wynik:
1
0


Dodane przez:Michael Suchacz
Data dodania:2009-07-26
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.