یک کاشی به مجموعه ای از خانههای یک جدول $h' \times w'$ گفته میشود. خانههای هر کاشی همبنداند. به عبارت دیگر رخ شطرنج میتواند از هر خانهیک کاشی به هر خانه دیگر آن برود و تنها از خانههای کاشی عبور کند.
به وحید کاشیکار، $k$ تا کاشی یکسان دادهاند و گفتهاند آی وحید! تا شب این کاشیها را در یک جدول $h \times w$ بچین. نه میتوانی کاشیها را بچرخانی، نه میتوانی شکلهای ناهمبند بسازی و نه آنها را روی هم بگذاری. ببینیم چند تا شکل میتوانی بسازی. بجنب!
از آنجا که وحید در بچگی برای المپیاد تمرین میکرد، فهمید که اگر دو شکل با انتقال به هم تبدیل شوند، یکسان محسوب میشوند. حال شما برای وحید کاشیکار، یک برنامه بنویسید که تعداد اشکال مختلفی که وحید میتواند بسازد را بشمارد.
در خروجی باید تعداد شکلهای متفاوتی که وحید کاشیکار میتواند بسازد را بنویسید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 193 3 82 13 100 | 0 |
| 1000000 3 100 92 77 | 9 |