{"problem":{"name":"Placing Squares","description":{"content":"Joisino has a bar of length $N$, which has $M$ marks on it. The distance from the left end of the bar to the $i$\\-th mark is $X_i$. She will place several squares on this bar. Here, the following cond","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc013_e"},"statements":[{"statement_type":"Markdown","content":"Joisino has a bar of length $N$, which has $M$ marks on it. The distance from the left end of the bar to the $i$\\-th mark is $X_i$.\nShe will place several squares on this bar. Here, the following conditions must be met:\n\n*   Only squares with integral length sides can be placed.\n*   Each square must be placed so that its bottom side touches the bar.\n*   The bar must be completely covered by squares. That is, no square may stick out of the bar, and no part of the bar may be left uncovered.\n*   The boundary line of two squares may not be directly above a mark.\n\n![image](https://atcoder.jp/img/agc013/placing_example.jpg)Examples of arrangements that satisfy/violate the conditions\n\nThe _beauty_ of an arrangement of squares is defined as the **product** of the areas of all the squares placed. Joisino is interested in the sum of the beauty over all possible arrangements that satisfy the conditions. Write a program to find it. Since it can be extremely large, print the sum modulo $10^9+7$.\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\leq N \\leq 10^9$\n*   $0 \\leq M \\leq 10^5$\n*   $1 \\leq X_1 < X_2 < ... < X_{M-1} < X_M \\leq N-1$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $X_2$ $...$ $X_{M-1}$ $X_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc013_e","tags":[],"sample_group":[["3 1\n2","13\n\nThere are two possible arrangements:\n\n*   Place a square of side length $1$ to the left, and place another square of side length $2$ to the right\n*   Place a square of side length $3$\n\nThe sum of the beauty of these arrangements is $(1 \\times 1 \\times 2 \\times 2) + (3 \\times 3) = 13$."],["5 2\n2 3","66"],["10 9\n1 2 3 4 5 6 7 8 9","100"],["1000000000 0","693316425"]],"created_at":"2026-03-03 11:01:14"}}