index.md

逛街

\begin{figure}[h] \centering \includegraphics[width=12cm]{img.jpg} \caption{四膳良子在購物時將一排衣服打包帶走，出自動畫電影《蠟筆小新：春日部野生王國》} \end{figure}

身為雙葉市新任里長，同時也是激進環保組織SKBE領導人的四膳守，對於保護地球環境有著病態的執著，甚至一手策畫了《人類動物化計畫》，打算把所有人變成動物。
然而他的妻子四膳良子卻對節能、保護環境一點興趣都沒有，不僅不分類垃圾也不節省洗澡水，更是揮霍無度地購買各種名牌服飾。

這天良子來到了一條專賣名牌奢侈品的商店街購物，已知商店街長度為 $m$ ，在街上每間隔單位長度開設一間店（包含頭尾），共有 $m + 1$ 間店，依序編號為 $0,~1,2,\dots,~m$。
良子在購物時有個特殊習慣，只要有經過的店她都會進去看看，也就是在逛完一間店後，她會從左右相鄰的店中選擇一間繼續逛（可以逛之前逛過的店，但不會繼續待在同一間店）。
這次良子打算從編號 $s$ 的店開始逛，最後逛完編號 $e$ 的店後回家，過程中總共逛了 $k$ 間店（包含重複），請問她有多少種可能的逛街行程？

\clearpage

輸入

一行包含四個整數 $m,~s,~e,~k$。
$m$ 代表商店街長度，$s$ 代表第一間店的編號，$e$ 代表最後一間店的編號，$k$ 代表逛了多少間店。

輸出

輸出有多少種逛街行程mod $1000000007$ 。

輸入限制

• $2 \leq k \leq 10^6$
• $1 \leq m \leq 10^6$
• $0 \leq s,~e \leq m$

子任務

\subtasks

\clearpage

範例輸入 1

\testfile{0-01.in}

範例輸出 1

\testfile{0-01.out}

範例輸入 2

\testfile{0-02.in}

範例輸出 2

\testfile{0-02.out}