გაფერადება

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: IBSU, 2014, ზამთრის ოლიმპიადა, X-XII


 

ცოტნეს მოსწყინდა ტრადიციული სათამაშოებით თამაში და ახალი გასართობი მოიგონა: იგი ყოველდღიურად უჯრებიან ფურცელზე ხაზავდა NxM რაოდენობის უჯრის შემცველ მართკუთხედს და მასში ზოგიერთ უჯრებს აფერადებდა. აღსანიშნავია, რომ ყოველ მომდევნო დღეს ცოტნეს წინა დღეებისაგან განსხვავებული ნახატი გამოსდიოდა. ასე, რომ სულ მან 2NM ნახატი შექმნა (ქვემოთ მოცემულია მის მიერ შექმნილი ნახატები, რომლებზეც გაფერადებული უჯრედები რუხი ფერითაა აღნიშნული).

 

ანასტასიამ გადაწყვიტა ცოტნესთან ერთად გართობილიყო: იგი ყოველდღე იღებდა ცოტნეს მორიგ ნახატს და ცდილობდა გაუფერადებელი უჯრები 1x2 ზომის მართკუთხედებით დაეფარა (ამასთან, ნახატის ყოველი გაუფერადებელი უჯრა უნდა დაიფაროს, მართკუთხედი არ შეიძლება ფარავდეს გაფერადებულ უჯრას და მართკუთხედები არ შეიძლება გადიოდნენ ნახატის ფარგლებს გარეთ და არ შეიძლება იკვეთებოდნენ).

 

რა თქმა უნდა, ანასტასიას ყოველთვის არ გამოსდიოდა ამის გაკეთება (ის შემთხვევები, როცა მან ეს შესძლო, როცა N=2 და M=2, ზემოთაა ნაჩვენები. ყურადღება მიაქციეთ იმას, რომ ნახატი დაფარულად ითვლება მაშინაც, როცა მისი ყველა უჯრა გაფერადებულია) და აინტერესებს, რამდენჯერ მოხდება ეს.

დაეხმარეთ მას და დაწერეთ პროგრამა, რომელიც დაადგენს იმ ნახატების რაოდენობას, რომელთა დაფარვასაც შესძლებს ანასტასია ზემოთ აღწერილი წესების დაცვით.

შესატანი მონაცემები:

სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ერთი ჰარით გაყოფილი ორი მთელი დადებითი N და M რიცხვი (1N6, 1M500) თითოეული ნახატის ზომა.

გამოსატანი მონაცემები:

სტანდარტული გამოტანის ერთადერთ სტრიქონში გამოიტანეთ ერთი მთელი დადებითი რიცხვი – ანასტასიას მიერ დაფარული ნახატების რაოდენობა მოდულით 109+7.

 

 

 




მაგალითები

შესატანი მონაცემები
2 2 2 3 დაკოპირება
გამოსატანი მონაცემები
6 18 დაკოპირება

შენიშვნა

ტესტების 20%-ში N·M ≤ 10;

ტესტების 20%-ში N·M ≤ 20.