{"problem":{"name":"D. Flags","description":{"content":"When Igor K. was a freshman, his professor strictly urged him, as well as all other freshmen, to solve programming Olympiads. One day a problem called \"Flags\" from a website called Timmy's Online Judg","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF93D"},"statements":[{"statement_type":"Markdown","content":"When Igor K. was a freshman, his professor strictly urged him, as well as all other freshmen, to solve programming Olympiads. One day a problem called \"Flags\" from a website called Timmy's Online Judge caught his attention. In the problem one had to find the number of three-colored flags that would satisfy the condition... actually, it doesn't matter. Igor K. quickly found the formula and got the so passionately desired Accepted.\n\nHowever, the professor wasn't very much impressed. He decided that the problem represented on Timmy's Online Judge was very dull and simple: it only had three possible colors of flag stripes and only two limitations. He suggested a complicated task to Igor K. and the fellow failed to solve it. Of course, we won't tell anybody that the professor couldn't solve it as well.\n\nAnd how about you? Can you solve the problem?\n\nThe flags consist of one or several parallel stripes of similar width. The stripes can be one of the following colors: white, black, red or yellow. You should find the number of different flags with the number of stripes from _L_ to _R_, if:\n\n*   a flag cannot have adjacent stripes of one color;\n*   a flag cannot have adjacent white and yellow stripes;\n*   a flag cannot have adjacent red and black stripes;\n*   a flag cannot have the combination of black, white and red stripes following one after another in this or reverse order;\n*   symmetrical flags (as, for example, a WB and a BW flag, where W and B stand for the white and black colors) are considered the same.\n\n## Input\n\nThe only line contains two integers _L_ and _R_ (1 ≤ _L_ ≤ _R_ ≤ 109). They are the lower and upper borders of the number of stripes on the flag.\n\n## Output\n\nPrint a single number — the number of different flags that would satisfy the condition of the problem and would have from _L_ to _R_ stripes, modulo 1000000007.\n\n[samples]\n\n## Note\n\nIn the first test the following flags exist (they are listed in the lexicographical order, the letters B, R, W, Y stand for Black, Red, White and Yellow correspondingly):\n\n3 stripes: BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY (overall 11 flags).\n\n4 stripes: BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY (12 flags).\n\nThat's why the answer to test 1 is equal to 11 + 12 = 23.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"当 Igor K. 还是大一新生时，他的教授严格敦促他以及所有其他新生参加编程竞赛。有一天，一个名为 \"Flags\" 的问题引起了他注意，该问题来自一个名为 Timmy's Online Judge 的网站。该问题要求找出满足某种条件的三色旗帜的数量……实际上，这无关紧要。Igor K. 迅速找到了公式，并得到了他热切渴望的 Accepted。\n\n然而，教授并不太满意。他认为 Timmy's Online Judge 上的这个问题非常枯燥简单：它只有三种可能的旗帜条纹颜色和两个限制条件。于是他给 Igor K. 提出了一个更复杂的问题，而这位学生未能解决。当然，我们不会告诉任何人教授自己也未能解决它。\n\n那么你呢？你能解决这个问题吗？\n\n旗帜由一个或多个宽度相同的平行条纹组成。条纹可以是以下四种颜色之一：白色、黑色、红色或黄色。你需要找出满足以下条件、条纹数量在 #cf_span[L] 到 #cf_span[R] 之间的不同旗帜的数量：\n\n输入仅包含一行，包含两个整数 #cf_span[L] 和 #cf_span[R]（#cf_span[1 ≤ L ≤ R ≤ 109]），分别表示旗帜条纹数量的下界和上界。\n\n请输出一个数——满足题目条件且条纹数量在 #cf_span[L] 到 #cf_span[R] 之间的不同旗帜数量，对 #cf_span[1000000007] 取模。\n\n在第一个测试用例中，以下旗帜存在（按字典序列出，字母 B、R、W、Y 分别代表黑色、红色、白色和黄色）：\n\n3 条纹：BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY（共 11 面旗帜）。\n\n4 条纹：BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY（12 面旗帜）。\n\n因此，第一个测试用例的答案为 #cf_span[11 + 12 = 23]。\n\n## Input\n\nThe only line contains two integers #cf_span[L] and #cf_span[R] (#cf_span[1 ≤ L ≤ R ≤ 109]). They are the lower and upper borders of the number of stripes on the flag.\n\n## Output\n\nPrint a single number — the number of different flags that would satisfy the condition of the problem and would have from #cf_span[L] to #cf_span[R] stripes, modulo #cf_span[1000000007].\n\n[samples]\n\n## Note\n\nIn the first test the following flags exist (they are listed in the lexicographical order, the letters B, R, W, Y stand for Black, Red, White and Yellow correspondingly):3 stripes: BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY (overall 11 flags).4 stripes: BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY (12 flags).That's why the answer to test 1 is equal to #cf_span[11 + 12 = 23].","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ C = \\{W, B, R, Y\\} $ be the set of 4 colors.  \nLet $ f(n) $ denote the number of valid flags with exactly $ n $ stripes, where no two adjacent stripes have the same color.\n\n**Constraints**  \n$ 1 \\leq L \\leq R \\leq 10^9 $\n\n**Objective**  \nCompute:  \n$$\n\\sum_{n=L}^{R} f(n) \\mod 1000000007\n$$  \nwhere $ f(1) = 4 $, and for $ n \\geq 2 $, $ f(n) = 4 \\cdot 3^{n-1} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF93D","tags":["dp","math","matrices"],"sample_group":[["3 4","23"],["5 6","64"]],"created_at":"2026-03-03 11:00:39"}}