Məyus növbə#6618
Fredinin bağındakı tualet xarab olub, buna görə də onun yeganə seçimi yaxınlıqdakı ictimai tualetlərdir. Bir dəfə tualetin qarşısında uzun bir sıra insan düzülüb. Fredinin təcili ehtiyacı var və buna görə də o, sıranın mümkün qədər tez irəliləməsini istəyir.
Tualetdən istifadə etmək üçün kron ödəmək lazımdır. Sıradakı insanların yarısının kronluq sikkəsi var, digər yarısının isə yalnız kronluq sikkəsi var. Əvvəlcə tualet operatorunun heç bir sikkəsi yoxdur, buna görə də sıradakı insanlar elə təşkil olunmalıdır ki, hər dəfə kimsə kronluq sikkə ilə ödəmək istəyəndə operatorun əvvəlki müştərilərdən ən azı bir kronluq sikkəsi olsun.
Problem ondadır ki, sıradakı bəzi insanlar öz yerlərini dəyişmək istəmirlər. İstəyən insanların öz mövqelərini dəyişdirə biləcəyi neçə üsul olduğunu müəyyən edin ki, operatorun həmişə qaytarmaq üçün pulu olsun. İstəməyənlərin mövqeləri dəyişdirilə bilməz (onları nə daha gec, nə də daha erkən yerə köçürmək olmaz). Üstəlik, mövqelərini dəyişmək istəyənlər arasında eyni sikkəsi olanların nisbi sırası qorunmalıdır.
Bir neçə testdən ibarətdir. Hər test n~(n \le 1000) uzunluğunda boş olmayan dairəvi mötərizələr və nöqtələrdən ibarət bir sətirdən ibarətdir. Nöqtə sıradakı mövqeyini dəyişmək istəyən bir insanı göstərir, açıq mötərizə mövqeyini dəyişmək istəməyən və kronluq sikkəsi olan bir insanı, bağlayıcı mötərizə isə mövqeyini dəyişmək istəməyən və kronluq sikkəsi olan bir insanı göstərir.
-in cüt olduğunu və sətirdə ən çox açıq mötərizə və ən çox bağlayıcı mötərizə olduğunu düşünün.
Hər test üçün, məsələnin şərtlərində təsvir olunan şərtlərə uyğun olaraq sıranı yenidən təşkil etməyin yollarının sayını hesablayın. Bu rəqəm çox böyük ola biləcəyi üçün, yalnız bir sətir içərisində ədədi təmsil etmənin son rəqəmini verin.
Nümunə 1