LETTER AGREEMENT

Exhibit 10.4

LETTER AGREEMENT

[Date]

The Gannett Board of Directors has approved an award of restricted stock (or deferred restricted stock if you have previously elected to defer this award) to you under the 2001 Omnibus Incentive Compensation Plan, as set forth below.

This Letter Agreement and the enclosed Terms and Conditions effective as of [date], constitute the formal agreement governing this award.

Please sign both copies of this Letter Agreement to evidence your agreement with the terms hereof. Keep one copy and return the other to the undersigned.

Please keep the enclosed Terms and Conditions for future reference. Until further notice they will apply to any future grants you receive.

Number of Shares:

Vesting Schedule:                                shares per month, commencing [1^st Month after Grant Date]

RESTRICTED STOCK

TERMS AND CONDITIONS FOR DIRECTORS

Under the

Gannett Co., Inc.

2001 Omnibus Incentive Compensation Plan

These Terms and Conditions, dated [date], govern the grant of restricted stock, including the deferred delivery of stock, (in both cases referred to as “Restricted Stock”) under the 2001 Omnibus Incentive Compensation Plan (the “Plan”) to Gannett directors (each a “Holder”), as set forth below. Terms used herein that are defined in the Plan shall have the meaning ascribed to them in the Plan. If there is any inconsistency between the defined terms of these Terms and Conditions and the terms of the Plan, the Plan’s terms shall supersede and replace the conflicting terms herein.

1. Grant of Restricted Stock. Pursuant to the provisions of (i) the Plan, (ii) the individual Letter Agreements governing each grant, and (iii) these Terms and Conditions, the Company has granted to the Holder the number of shares of common stock of the Company (“Common Stock”) in the applicable Letter Agreement and subject to the restrictions set forth therein and in these Terms and Conditions. If the Holder has previously made an election under the Company’s Deferred Compensation Plan to defer receipt of the stock pursuant to this grant of Restricted Stock, the issuance of shares pursuant to this grant will be deferred in accordance with the Holder’s election and this grant will be deferred Restricted Stock.

2. Forfeiture. Upon a Holder’s ceasing to be a Director of the Company for any reason, any shares of Restricted Stock that remain unvested shall be forfeited to the Company, or in the case of deferred Restricted Stock, shall not be issued.

3. Delivery of Share Certificates. Certificates for vested shares will be delivered to the Holder upon the Holder’s ceasing to be a Director of the Company. In the case of the death of a Director during the term of his or her directorship, certificates for vested shares will be delivered to the Holder’s beneficiary in accordance with Section 11 of the Plan. In the case of deferred Restricted Stock, certificates with regard to vested shares will be delivered to the Holder in accordance with the Holder’s election under the Company’s Deferred Compensation Plan, but no earlier than the termination of the Holder’s directorship.

-2-

4. Non-Assignability. Restricted Stock may not be transferred, assigned, pledged or hypothecated, whether by operation of law or otherwise, nor be made subject to execution, attachment or similar process until certificates for vested shares have been delivered to the Holder upon the Holder’s ceasing to be a Director of the Company.

5. Rights as a Shareholder. A Holder who has not elected deferred Restricted Stock shall have the right to vote the shares of Restricted Stock and to receive dividends on the Restricted Stock as of the grant date. In the case of deferred Restricted Stock, the Holder shall have no rights as a shareholder until such time as share certificates are issued in the name of the Holder in accordance with the Company’s Deferred Compensation Plan. However, the Holder will be credited with amounts equivalent to the dividends on the deferred Restricted Stock pursuant to the Company’s Deferred Compensation Plan.

6. Discretionary Plan. The Plan is discretionary in nature and may be suspended or terminated by the Company at any time. With respect to the Plan, (a) each grant of Restricted Stock is a one-time benefit which does not create any contractual or other right to receive future grants of Restricted Stock, or benefits in lieu of Restricted Stock; (b) all determinations with respect to any such future grants, including, but not limited to, the times when Restricted Sock shall be granted, the number of shares subject to each grant, and the times when Restricted Stock becomes vested, will be at the sole discretion of the Company; (c) the Holder’s participation in the Plan is voluntary; (d) the Restricted Stock is not part of normal and expected compensation for purposes of calculating any severance, resignation, redundancy, end of service payment, bonuses, long-service awards, pension or retirement benefits, or similar payments; and (e) the future value of the Restricted Stock is unknown and cannot be predicted with certainty.

7. Section 83(b) Election. A Holder who elects to receive Restricted Stock that is not deferred (i.e., does not make an election to defer this award under the Company’s Deferred Compensation Plan) may wish to consider an election under Section 83(b) of the Internal Revenue Code of 1986, as amended (the “Code”). Under Section 83 of the Code, the fair market value of the Restricted Stock on the date the forfeiture restrictions applicable to such shares lapse will be reportable as ordinary income at that time. The Holder may elect to be taxed at the time the Restricted Stock is acquired rather than when such shares cease to be subject to such forfeiture restrictions by filing an election under Code Section 83(b) with the Internal Revenue

-3-

Service within thirty (30) days after the Grant Date. The Holder will have to make a tax payment based on the fair market value of the shares on the grant date. Holders of deferred Restricted Stock do not need to (and cannot) make Section 83(b) elections.

8. Effect of Plan. The Plan is hereby incorporated by reference into these Terms and Conditions, and these Terms and Conditions are subject in all respects to the provisions of the Plan, including without limitation the authority of the Committee to adjust awards and to make interpretations and other determinations with respect to all matters relating to these Terms and Conditions, the applicable Letter Agreements, the Plan, and awards made pursuant thereto. These Terms and Conditions shall apply to grants of Restricted Stock made to the Holder from the date hereof until such time as revised Terms and Conditions are effective.

9. Notice. Notices hereunder shall be in writing and if to the Company shall be addressed to the Secretary of the Company at 7950 Jones Branch Drive, McLean, Virginia 22107 and if to the Holder shall be addressed to the Holder at his or her address as it appears on the Company’s records.

10. Successors and Assigns. The applicable Letter Agreement and these Terms and Conditions shall be binding upon and inure to the benefit of the successors and assigns of the Company and, to the extent provided in Section 3 hereof, to the heirs, legatees and personal representatives of the Holder.

11. Change in Control Provisions. Notwithstanding anything to the contrary in these Terms and Conditions, the following provisions shall apply to the Restricted Stock granted under the attached Letter Agreement:

(a) Definitions. As used in Article 15 of the Plan and in these Terms and Conditions, a “Change in Control” shall mean the first to occur of the following:

(i) the acquisition by any individual, entity or group (within the meaning of Section 13(d)(3) or 14(d)(2) of the Exchange Act) (a “Person”) of beneficial ownership (within the meaning of Rule 13d-3 promulgated under the Exchange Act) of 20% or more of either (A) the then-outstanding shares of common stock of the Company (the “Outstanding Company Common Stock”) or (B) the combined voting power of the then-outstanding voting securities of the Company entitled to vote generally in the election of

-4-

directors (the “Outstanding Company Voting Securities”); provided, however, that, for purposes of this Section, the following acquisitions shall not constitute a Change in Control: (i) any acquisition directly from the Company, (ii) any acquisition by the Company, (iii) any acquisition by any employee benefit plan (or related trust) sponsored or maintained by the Company or one of its affiliates or (iv) any acquisition pursuant to a transaction that complies with Sections 11(a)(iii)(A), 11(a)(iii)(B) and 11(a)(iii)(C);

(ii) individuals who, as of the date hereof, constitute the Board (the “Incumbent Board”) cease for any reason to constitute at least a majority of the Board; provided, however, that any individual becoming a director subsequent to the date hereof whose election or nomination for election by the Company’s stockholders was approved by a vote of at least a majority of the directors then comprising the Incumbent Board shall be considered as though such individual were a member of the Incumbent Board, but excluding, for this purpose, any such individual whose initial assumption of office occurs as a result of an actual or threatened election contest with respect to the election or removal of directors or other actual or threatened solicitation of proxies or consents by or on behalf of a Person other than the Board;

(iii) consummation of a reorganization, merger, statutory share exchange or consolidation or similar corporate transaction involving the Company or any of its subsidiaries, a sale or other disposition of all or substantially all of the assets of the Company, or the acquisition of assets or stock of another entity by the Company or any of its subsidiaries (each, a “Business Combination”), in each case, unless, following such Business Combination, (A) all or substantially all of the individuals and entities that were the beneficial owners of the Outstanding Company Common Stock and the Outstanding Company Voting Securities immediately prior to such Business Combination beneficially own, directly or indirectly, more than 50% of the then-outstanding shares of common stock and the combined voting power of the then-outstanding voting securities entitled to vote generally in the election of directors, as the case may be, of the corporation or entity resulting from such Business Combination (including, without limitation, a corporation or entity that, as a result of such transaction, owns the Company or all or substantially all of the Company’s assets either directly or through one or more subsidiaries) in substantially the same proportions as their ownership immediately prior to such Business Combination of the Outstanding Company Common Stock and the Outstanding

-5-

Company Voting Securities, as the case may be, (B) no Person (excluding any employee benefit plan (or related trust) of the Company or any corporation or entity resulting from such Business Combination) beneficially owns, directly or indirectly, 20% or more of, respectively, the then-outstanding shares of common stock of the corporation or entity resulting from such Business Combination or the combined voting power of the then-outstanding voting securities of such corporation or entity, except to the extent that such ownership existed prior to the Business Combination, and (C) at least a majority of the members of the board of directors of the corporation or entity resulting from such Business Combination were members of the Incumbent Board at the time of the execution of the initial agreement or of the action of the Board providing for such Business Combination; or

(iv) approval by the stockholders of the Company of a complete liquidation or dissolution of the Company.

No Participant in the Plan who participates in any group conducting a management buyout of Gannett under the terms of which Gannett ceases to be a public company may claim that such buyout is a Change in Control under the Plan and no such Participant shall be entitled to any payments or other benefits under the Plan as a result of such buyout.

(b) Acceleration Provisions. In the event of the occurrence of a Change in Control, all shares of Restricted Stock shall become immediately fully vested. The benefits that may accrue to the Holder under this Section may be affected by the “Limited Vesting” provisions of Sections 15.3 and 15.4 of the Plan.

(c) Legal Fees. The Company shall pay all legal fees, court costs, fees of experts and other costs and expenses when incurred by the Holder in connection with any actual, threatened or contemplated litigation or legal, administrative or other proceedings involving the provisions of this Section 11, whether or not initiated by the Holder.

12. Applicable Laws and Consent to Jurisdiction. The validity, construction, interpretation and enforceability of this Agreement shall be determined and governed by the laws of the State of Delaware without giving effect to the principles of conflicts of law. For the purpose of litigating any dispute that arises under this Agreement, the parties hereby consent to exclusive jurisdiction in Virginia and agree that such litigation shall be conducted in the courts of Fairfax County, Virginia or the federal courts of the United States for the Eastern District of Virginia.

-6-