{"code":"rgb","name":"Tô màu RGB","description":"[user:CaiWinDao] có một cái tháp $N$ tầng. Anh sẽ tô màu mỗi tầng của tháp bằng một trong 3 màu: đỏ, xanh dương, xanh lá hoặc không tô. Đồng thời, anh cũng định nghĩa độ đẹp của tháp như sau:\r\n\r\nĐộ đẹp của tháp bằng tổng độ đẹp của $N$ tầng. Trong đó, độ đẹp của tầng màu đỏ là $A$, xanh là là $A + B$, xanh dương là $B$, và $0$ nếu không được tô. Ở đây, $A, B$ là các số được cho trước. \r\n\r\n[user:CaiWinDao] rất thích con số $40529042905$ nên muốn độ đẹp của cái tháp cũng là $40529042905$. Tuy nhiên, [user:CaiWinDao] cho rằng con số này không có ý nghĩa toán học gì (mà chỉ có ý nghĩa về tinh thần) nên đã thay nó bằng một số $K$. Anh tự hỏi rằng, có bao nhiêu cách tô màu sao cho độ đẹp của tháp đúng bằng $K$? Hai cách tô được xem là khác nhau nếu có một tầng được tô màu khác nhau trong hai cách.\r\n\r\n#### Input\r\nGồm một dòng chứa bốn số nguyên $N, A, B, K \\ ( 1 \\leq N \\leq 3 \\times 10^5, 1 \\leq A,B \\leq 3 * 10^5, 0 \\leq K \\leq 18 \\times 10^{10})$\r\n\r\n#### Output\r\nIn ra số cách tô $mod \\ 998244353$\r\n\r\n#### Example \r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 1 2 5\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        40\r\n        ```\r\n        \r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 5 6 0\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n\r\n!!! question \"Test 3\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        90081 33447 90629 6391049189\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        577742975\r\n        ```\r\n-----\r\n*Nguồn: AtCoder*","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}