TopCoder

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

37.8% (14/37)

Description

Fuko的姊姊(據說叫做Kouko)終於帶著Fuko滿滿的祝福(沒有6的海星)結婚了,而在之後為了避免打擾姊姊幸福的新婚生活,Fuko決定獨自搬出去住,於是到處向人打聽哪裡有便宜的住所。

突然有一天,就讀於光坂學園(與Fuko同校)三年E班的班長Kyou突然跑來跟Fuko說學生宿舍很便宜,而且管理員Misae小姐人好又溫柔,於是Fuko就毅然決然決定要搬入學生宿舍。

Kyou帶著Fuko來到了學生宿舍,碰巧遇到管理員Misae小姐正在傷腦筋,於是兩人便上前問問,才知道Misae小姐正為了安排房間的事情苦惱著,古道熱腸的Fuko決定要幫助員Misae小姐,Misae聽了十分開心,並允諾Fuko如果成功幫忙解決,就可以不必繳宿舍費,Fuko聽了更是心動了,於是就和Kyou兩人一同坐下,聆聽Misae小姐的問題。

Misae小姐的問題是這樣的:

住在學生宿舍的學生有主要分為兩種,一種是有參加社團的人(基本上光坂學園半強迫性加入社團,所以不加入很奇怪),一種是如Youhei等不等願意參加社團的怪人(不巧,Fuko剛好認識一名名為Okasaki討厭的大怪人,所以更想要幫助Misae小姐了),而通常怪人因為不參加社團活動(這樣就空了一節課,他們會拿去做什麼呢?),所以喜歡做一些糟糕的事情(Misae小姐推測)。

目前總共有n種社團的學生可能會住在宿舍裡,為了避免怪人變的更糟糕,Misae小姐決定怪人居住的房間至少要相隔m間(光坂學園的學生宿舍只有一層,並且所有房間(共有k間)都在同一側排成一列),以免怪人們『兩個大怪人,一個糟糕人』的情況發生,而Misae小姐希望知道符合這種情形的房間分配方法會有幾種情況

由於Misae小姐曾經擔任過傳說中的學生會長,並且曾經達到一週無遲到早退的傳奇紀錄(經由現任學生會長Tomoyo得知),所以被幻想世界的少女(據說叫做Ushio)賜與了神奇的能力,只要得知一個數字除以p的餘數就可以知道該數字,所以FukoKyou只要跟Misae小姐回報結果除以p的餘數就可以了

FukoKyou的數學都沒有很好(聽說Kyou的妹妹Ryou功課很好,不過現在沒有時間去請教她了),聰明的你,能幫助他們嗎?

還有,如果在做題前說一聲:『Kyou Hujibayashi Moe』,也許會對做題有些幫助也說不定!

Input Format

輸入可能包含多筆測試資料,每筆測試資料佔一列,包含四個以空白間格的正整數
n表光坂學園社團的個數(1<=n<=65536)
m表Misae小姐希望怪人們相隔的房間數(0<=m<=512)
k表光坂學園學生宿舍房間的數量(1<=k<=65536)
p表Misae小姐能力中的除數(1<=p<231)
當n=m=k=p=0時,請結束程式,聰明的你當然不會對他做出任何動作!

Output Format

每筆資料輸出一列,共有一個數字,代表方法數除以p的餘數。

Sample Input

2 2 5 1000
0 0 0 0

Sample Output

136

Hints

[房間] [房間] [房間] [房間] [房間]

首先先分類討論:

沒有怪人的情況:2*2*2*2*2=32 (種)

一個怪人的情況:
 可能有:

1. [怪人] [房間] [房間] [房間] [房間]:2*2*2*2=16 (種)

2. [房間] [怪人] [房間] [房間] [房間]:2*2*2*2=16 (種)

3. [房間] [房間] [怪人] [房間] [房間]:2*2*2*2=16 (種)

4. [房間] [房間] [房間] [怪人] [房間]:2*2*2*2=16 (種)

5. [房間] [房間] [房間] [房間] [怪人]:2*2*2*2=16 (種)

兩個怪人的情況:
 可能有:

1. [怪人] [房間] [房間] [怪人] [房間]:2*2*2=8 (種)

2. [怪人] [房間] [房間] [房間] [怪人]:2*2*2=8 (種)

3. [房間] [怪人] [房間] [房間] [怪人]:2*2*2=8 (種)

故答案為32+16+16+16+16+16+8+8+8=136 (種)

※更詳細的資料請參考這裡

Problem Source

原TIOJ1201 / TIOJ 2008例行賽02 (prob C)。Problem Setter: hallogameboy。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144