Թռիչքների կանխատեսում

օդանավակայաններ կազմել են միություն։ Միությունը իր խնդիրն է դարձրել պարզել, թե որ օդանավակայաններն են հնարավոր ամենածանրաբեռնվածները՝ հետագա նախագծերում այդ փաստը հաշվի առնելու համար։ Այդ հարցով նրանք դիմել են Ձեզ։

Օդանավակայանները համարակալված են -ից թվերով։ Ձեզ տրված է նաև իրար հետ ուղիղ կապ պահպանող օդանավակայանների զույգերի ցանկը։

-րդ օդանավակայանում տվյալ պահին տեղակայված է ինքնաթիռ։ Յուրաքանչյուր օդային թռիչքի սկզբնական և վերջնական կայանները պետք է կա՛մ իրար հետ ուղիղ կապ պահպանեն, կա՛մ ունենան մեկ այլ ընդհանուր իրենց հետ կապ ունեցող օդանավակայան։ Միության որոշմամբ յուրաքանչյուր ինքնաթիռ ամեն օր կատարում է ճիշտ մեկ թռիչք կամ թռիչք չի կատարում, եթե այն իրականացնելը անհնար է։

Հարկավոր է գրել ծրագիր, որը կպատասխանի հարցումների, թե համարի օդանավակայան օր հետո քանի տարբեր ժամանման տարբերակներ կան։ Ժամանման տարբերակները կհամարենք տարբեր, եթե ժամանող ինքնաթիռն է տարբեր, կամ եթե նույն ինքնաթիռն է ժամանում, բայց տարբերակների թռիչքային պատմությունները տարբեր են (տես օրինակի բացատրությունը)։ Քանի որ այդ թիվը կարող է շատ մեծ լինել, պետք է արտածել ժամանման տարբերակների քանակի ֊ի բաժանելիս ստացվող մնացորդը։

Մուտքային տվյալներ

Առաջին տողում տրված են ամբողջ թվերը՝ համապատասխանաբար օդանավակայանների, ուղիղ կապված զույգերի և հարցումների քանակները։

Հաջորդող տողում տրված են հատ ամբողջ թվեր՝ -րդ օդանավակայանում տեղակայված ինքնաթիռների քանակը։

Հաջորդող տողերում տրված են չկրկնվող ուղիղ կապ պահպանող կայանների համարների զույգերը։

Հաջորդող տողերում տրված են հերթական հարցման համապատասխան ամբողջ թվերը։

Ելքային տվյալներ

Ամեն հարցման համար առանձին տողում հարկավոր է արտածել թիվ՝ հնարավոր ժամանման տարբերակների քանակի մնացորդը ֊ի բաժանելիս։

Ենթախնդիրներ

Օրինակ

5 3 2
0 2 1 1 0
1 4
3 2
2 1
4 2
5 3

6
0

Օրինակի պարզաբանումը․ Առաջին հարցումը պահանջում է հաշվել օր հետո համարի օդանավակայան ժամանելու տարբերակները։ Դրանք հետևյալն են․
երկրորդ օդանավակայանի առաջին ինքնաթիռով,
երկրորդ օդանավակայանի երկրորդ ինքնաթիռով,
երրորդ օդանավակայանի միակ ինքնաթիռով,
երրորդ օդանավակայանի միակ ինքնաթիռով,
չորրորդ օդանավակայանի միակ ինքնաթիռով,
չորրորդ օդանավակայանի միակ ինքնաթիռով։