{"problem":{"name":"Iroha and Haiku","description":{"content":"_Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order._ Iroha is looking for _$X,Y,Z$\\-Haiku_ (defined below) in integer sequences. Cons","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc058_c"},"statements":[{"statement_type":"Markdown","content":"_Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order._\nIroha is looking for _$X,Y,Z$\\-Haiku_ (defined below) in integer sequences.\nConsider all integer sequences of length $N$ whose elements are between $1$ and $10$, inclusive. Out of those $10^N$ sequences, how many contain an $X,Y,Z$\\-Haiku?\nHere, an integer sequence $a_0, a_1, ..., a_{N-1}$ is said to _contain an $X,Y,Z$\\-Haiku_ if and only if there exist four indices $x, y, z, w (0 ≦ x < y < z < w ≦ N)$ such that all of the following are satisfied:\n\n*   $a_x + a_{x+1} + ... + a_{y-1} = X$\n*   $a_y + a_{y+1} + ... + a_{z-1} = Y$\n*   $a_z + a_{z+1} + ... + a_{w-1} = Z$\n\nSince the answer can be extremely large, print the number modulo $10^9+7$.\n\n## Constraints\n\n*   $3 ≦ N ≦ 40$\n*   $1 ≦ X ≦ 5$\n*   $1 ≦ Y ≦ 7$\n*   $1 ≦ Z ≦ 5$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $X$ $Y$ $Z$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc058_c","tags":[],"sample_group":[["3 5 7 5","1\n\nHere, the only sequence that contains a $5,7,5$\\-Haiku is $[5, 7, 5]$."],["4 5 7 5","34"],["37 4 2 3","863912418"],["40 5 7 5","562805100"]],"created_at":"2026-03-03 11:01:14"}}