Luka รู้สึกเบื่อในคาบเรียนวิชาเคมี ดังนั้น เขาจึงจ้องมองไปยังตารางธาตุเคมีขนาดใหญ่ที่แขวนอยู่ที่กำแพงตรงเหนือกระดานดำและเพื่อเป็นการฆ่าเวลา   Luka จึงตัดสินใจที่จะสร้างตารางธาตุที่สมบูรณ์ของเขาขึ้นมาเอง ซึ่งแตกต่างจากอันที่แขวนอยู่ในห้องเรียน
ตาารางของเขาประกอบด้วย N คอลัมน์และในแต่ละคอลัมน์จะมีค่าความสูงของมันเอง โดยทุกคอลัมน์จะเรียงต่อกันที่ด้านล่างของตาราง ดังเช่นที่แสดงในรูปตัวอย่างด้านล่างนี้   หลังจากที่เขาวาดตารางของเขาขึ้นมาแล้ว เขาต้องการที่จะเติมธาตุต่าง ๆ ลงในช่องว่างของตาราง เริ่มแรก เขาตัดสินใจที่จะเติมแก๊สเฉื่อยจำนวน K ธาตุลงไป   และเขาต้องการที่จะใส่มันลงไปในตารางโดยที่จะต้องไม่ให้มีแก๊สเฉื่อย 2 แก๊สใด ๆ อยู่ใกล้กันและกันในตาราง
รูปสี่เหลี่ยม 2 รูปใด ๆ ในตารางจะถือว่า อยู่ใกล้กันและกัน   ถ้ารูปสี่เหลี่ยม 2 รูปนั้นอยู่ในคอลัมน์หรือแถวเดียวกันและต้องมีรูปสี่เหลี่ยมอื่น ๆ คั่นระหว่างรูปสี่เหลี่ยมทั้งสองนั้นด้วย  ในตัวอย่างด้านล่างนี้ รูปสี่เหลี่ยม “a” ถือว่าไม่อยู่ใกล้ซึ่งกันและกัน   ในขณะที่รูปสี่เหลี่ยม “b” ถือว่า อยู่ใกล้ซึ่งกันและกัน
 

งานของคุณ

จงเขียนโปรแกรมเพื่อรับค่า N, K และ ค่าความสูงในแต่ละ N คอลัมน์   แล้วคำนวณหาจำนวนวิธีทั้งหมดที่ Luka สามารถเติมแก๊สเฉื่อยลงไปในตารางได้   ซึ่งค่าผลลัพธ์ที่ได้นี้อาจมีค่ามาก   ดังนั้น ให้แสดงผลข้อมูลส่งออกโดย มอดุโล ค่านี้ด้วย 1000000007

ข้อมูลนำเข้า

ในบรรทัดแรก   ประกอบด้วยเลขจำนวนเต็ม N และ K ซึ่งคั่นกันด้วยช่องว่าง   โดย  N และ K มีค่าดังนี้
1 ≤ N ≤ 500 และ 1 ≤ K ≤ 500 ซึ่งหมายถึงจำนวนของคอลัมน์ในตารางของ Luka และจำนวนของแก๊สเฉื่อย ตามลำดับ
บรรทัดถัดไป   ประกอบด้วยเลขจำนวนเต็มบวก N ค่าและแยกกันโดยใช้ช่องว่าง   ซึ่งหมายถึงค่าความสูงในแต่ละคอลัมน์จากซ้ายไปขวา   โดยค่าความสูงเหล่านี้จะมีค่ามากที่สุด คือ 1000000

ข้อมูลส่งออก

ให้แสดงผลข้อมูลส่งออกด้วยผลลัพธ์ของจำนวนวิธีทั้งหมดที่ Luka สามารถเติมแก๊สเฉื่อยลงในตารางได้ มอดุโลด้วย 1000000007
 
การให้คะแนน
ในกรณีทดสอบ จะได้รับคะแนน 40 เปอร์เซ็นต์ของคะแนนทั้งหมด   ถ้าตัวเลขทั้งหมดในข้อมูลนำเข้ามีค่าน้อยกว่า 15
ในกรณีทดสอบ จะได้รับคะแนน 70 เปอร์เซ็นต์ของคะแนนทั้งหมด   ถ้าตัวเลขทั้งหมดในข้อมูลนำเข้ามีค่าน้อยกว่า 100

ที่มา: COCI 2008/2009, Contest #4 – January 17, 2009