TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

69.2% (18/26)

Tags

Description

建康中學(簡稱建中)是傳說中的「千湖中學」。建中的三年級學生們要畢業了,畢籌會正計劃著做一件「大事」--在學校內造一個大大的水坑。

為了達成目的,畢籌會決定蓋一條由2m段路連接起來的路徑,將兩個高度為n的高地連接起來,且這條路徑的正中間的高度為0. 如此一來,這條路徑就變成了一個碗狀,暴雨來襲時就會形成超級巨大的水坑。

美觀起見,畢籌會決定讓這條路是對稱的,所以如果要決定整個路徑的形狀,畢籌會只需要考慮從某一端的高地到中間的低地的路徑應該要長怎樣。假設這一段路徑中,第一段路的高度降低了a1, 第二段路的高度降低了a2, 以此類推,其中a1,a2,,am都是正整數。不難發現a1,a2,,am應該要滿足限制條件a1+a2++am=n. 除此之外,為了希望這個路徑看起來像個碗狀,畢籌會希望a12a2,a22a3,,am12am.

請問畢籌會有幾種方法蓋出這條路徑?

Input Format

每組測資只包含一行,含有兩個正整數n<2201,m20, 分別代表兩端高地以及中央低地的高度差以及某端高地至中央低地要由幾段路連接。

子任務(測資) 額外限制 分數
1 (0~4) n15 10
2 (5~9) n1000 40
3 (0~14) 50

Output Format

請輸出一個正整數,代表可行的方案個數。由於答案可能很大,請將答案模1000000007後輸出。

Sample Input 1

10 3

Sample Output 1

2

Hints

範例測資中,7+2+1以及6+3+1都是可行的方案。

Problem Source

Problem/Description by Paupière.
改編自2017 APMO P3.

Subtasks

No. Testdata Range Score
1 0~4 10
2 5~9 40
3 10~14 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 50 65536 262144 3
11 50 65536 262144 3
12 50 65536 262144 3
13 50 65536 262144 3
14 50 65536 262144 3